fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 20;
  5. const int maxm = 80;
  6. const ll LLINF = 1e18;
  7. int a[maxm+5][maxn+5], m, n;
  8. ll dp[maxm+5];
  9. void read() {
  10.     cin >> m >> n;
  11.     for (int i = 1; i<=m; ++i) {
  12.         for (int j = 1; j<=n; ++j) cin >> a[i][j];
  13.     }
  14. }
  15. void solve() {
  16.     for (int i = 1; i<=n; ++i) {
  17.         ll new_dp[maxm+5];
  18.         for (int j = 0; j<=m; ++j) new_dp[j] = 0;
  19.  
  20.         for (int j = 0; j<=m; ++j) {
  21.             for (int k = 0; k<=j; ++k) {
  22.                 new_dp[j] = max(new_dp[j], dp[j-k] + a[k][i]);
  23.             }
  24.         }
  25.         for (int j = 0; j<=m; ++j) dp[j] = new_dp[j];
  26.     }
  27.     ll res = 0;
  28.     for (int i = 0; i<=m; ++i) res = max(res, dp[i]);
  29.     cout << res;
  30. }
  31. int main() {
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(0); cout.tie(0);
  34.     read();
  35.     solve();
  36.     return 0;
  37. }
  38.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/b9w3tm
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!