fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define endl "\n"
  4. #define F first
  5. #define S second
  6. #define loop(a,n) for(int i=a; i<=n ; i++)
  7. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  8. #define NAME ""
  9. using namespace std;
  10.  
  11. int n, m, a[1001][1001], f[1001][1001];
  12.  
  13. void nhap(){
  14.     cin >> n >> m;
  15.     for(int i = 1;i <= n; ++i) {
  16.         for(int j = 1;j <= m;++j){
  17.             cin >> a[i][j];
  18.         }
  19.     }
  20. }
  21. void solve(){
  22.     for(int j = 0;j <= m; ++j) f[0][j] = 0;
  23.     for(int i = 1;i <= n; ++i){
  24.         for(int j = 1;j <= m; ++j){
  25.             f[i][j] = f[i][j-1];
  26.             if(i < j) {
  27.                 f[i][j] = max(f[i][j], f[i-1][j-1] + a[i][j]);
  28.             }
  29.         }
  30.     }
  31.     cout << f[n][m] << endl;
  32.  
  33.     vector<int> pos(n + 1);
  34.     int i = n, j = m;
  35.     while(i > 0 && j > 0){
  36.         if(f[i][j] == f[i][j-1]) {
  37.             --j;
  38.         } else {
  39.             pos[i] = j;
  40.             --i; --j;
  41.         }
  42.     }
  43.     for(int k = 1; k <= n; ++k){
  44.         cout <<  pos[k] << " ";
  45.     }
  46. }
  47.  
  48. int main(){
  49.     ios_base::sync_with_stdio(0);
  50.     cin.tie(0);cout.tie(0);
  51.     //freopen(NAME".INP","r",stdin);
  52.     //freopen(NAME".OUT","w",stdout);
  53.     nhap();
  54.     solve();
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gSeBYu
language:
C++ (gcc 8.3)
created:
1 day 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!