simushin_pavel

Untitled

Nov 24th, 2020
403
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <algorithm>
  5. using namespace std;
  6. int main(){
  7.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8.     long long n, m, i, j, temp; cin >> n >> m;
  9.     vector<pair<long long, long long>> way, minx(n), miny(n);
  10.     vector<vector<long long>> dp(n, vector<long long>(m)), a(n, vector<long long>(m)), px(n, vector<long long>(m, -1)), py(n, vector<long long>(m, -1));
  11.     for(i=0; i<n; ++i) for(j=0; j<m; ++j) cin >> a[i][j];
  12.     miny[0]={a[0][0], 0};
  13.     dp[0][0]=a[0][0];
  14.     minx[0]={a[0][0], 0};
  15.     for(i=1; i<m; ++i){
  16.         dp[0][i]=miny[0].first+a[0][i];
  17.         px[0][i]=miny[0].second;
  18.         py[0][i]=0;
  19.         if(dp[0][i]<miny[0].first){
  20.             miny[0].first=dp[0][i];
  21.             miny[0].second=i;
  22.         }
  23.         minx[i]={dp[0][i], 0};
  24.     }
  25.     for(i=1; i<n; ++i){
  26.         dp[i][0]=minx[0].first+a[i][0];
  27.         px[i][0]=0;
  28.         py[i][0]=minx[0].second;
  29.         if(dp[i][0]<minx[0].first){
  30.             minx[0].first=dp[i][0];
  31.             minx[0].second=i;
  32.         }
  33.         miny[i]={dp[i][0], 0};
  34.     }
  35.     for(i=1; i<n; ++i) for(j=1; j<m; ++j){
  36.         if(minx[j].first<miny[i].first){
  37.             dp[i][j]=minx[j].first+a[i][j];
  38.             px[i][j]=j;
  39.             py[i][j]=minx[j].second;
  40.         } else{
  41.             dp[i][j]=miny[i].first+a[i][j];
  42.             px[i][j]=miny[i].second;
  43.             py[i][j]=i;
  44.         }
  45.         if(dp[i][j]<miny[i].first){
  46.             miny[i].first=dp[i][j];
  47.             miny[i].second=j;
  48.         }
  49.         if(dp[i][j]<minx[j].first){
  50.             minx[j].first=dp[i][j];
  51.             minx[j].second=i;
  52.         }
  53.     }
  54.     for(i=n-1, j=m-1; i!=-1&&j!=-1; temp=i, i=py[i][j], j=px[temp][j]) way.push_back({i, j});
  55.     reverse(way.begin(), way.end());
  56.     cout << dp[n-1][m-1] << " " << way.size() << "\n";
  57.     for(i=0; i<way.size(); ++i) cout << way[i].first+1 << " " << way[i].second+1 << "\n";
  58.     return 0;
  59. }
RAW Paste Data