Advertisement
Josif_tepe

Untitled

Mar 17th, 2022
900
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <set>
  7. #include <cstring>
  8. using namespace std;
  9. int n,m;
  10. int mat[1000][1000];
  11. int dp[1000][1000];
  12. vector<pair<int, int> > v[1000];
  13. int main(){
  14.     ios_base::sync_with_stdio(false);
  15.     cin >> n >> m;
  16.     for (int i = 0; i < n; i++) {
  17.         for (int j = 0; j < m; j++) {
  18.             cin >> mat[i][j];
  19.         }
  20.     }
  21.     for(int i = 0; i < n - 1; i++) {
  22.         for(int j= 0; j < m; j++) {
  23.             v[i].push_back(make_pair(mat[i][j] + mat[i + 1][j], j));
  24.         }
  25.         sort(v[i].begin(), v[i].end());
  26.         reverse(v[i].begin(), v[i].end());
  27.     }
  28.     memset(dp,0,sizeof dp);
  29.     dp[0][0] = mat[0][0];
  30.     for (int i = 0; i < n-1; i++) {
  31.         for (int j = 0; j < m; j++) {
  32.             for (int k = 0; k < min(3, m) ; k++) {
  33.                 if(v[i][k].second != j) {
  34.                     dp[i + 1][v[i][k].second] = max(dp[i + 1][v[i][k].second], dp[i][j] + v[i][k].first);
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     int res = dp[n-1][m-1];
  40.     for(int i = 0; i < m-1; i++) {
  41.         if(n == 2 && i == 0){
  42.             continue;
  43.         }
  44.         res = max(res,dp[n-1][i] + mat[n-1][m-1]);
  45.  
  46.     }
  47.     cout << res;
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement