lucacodorean

numarare

Jan 29th, 2020
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <stack>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. ifstream fin("numarare.in");
  8. ofstream fout("numarare.out");
  9.  
  10. int a[101][101];
  11. stack<pair<int,int> >s;
  12.  
  13. int main()
  14. {
  15.     int n,m;
  16.     fin>>n>>m;
  17.  
  18.     for(int i=1; i<=n; i++)
  19.     {
  20.         for(int j=1; j<=m; j++)
  21.         {
  22.             fin>>a[i][j];
  23.         }
  24.     }
  25.  
  26.     for(int i=1; i<=m; i++)
  27.     {
  28.         a[1][i]+=max(a[1][i-1], a[0][i-1]);
  29.     }
  30.  
  31.     for(int j=1; j<=n; j++)
  32.     {
  33.         a[j][1]+=max(a[j-1][1], a[j-1][0]);
  34.     }
  35.  
  36.     for(int i=2; i<=n; i++)
  37.     {
  38.         for(int j=2; j<=m; j++)
  39.         {
  40.             a[i][j]+=max(a[i-1][j],a[i][j-1]);
  41.         }
  42.     }
  43.  
  44.  
  45.     for(int i=1; i<=n; i++)
  46.     {
  47.         for(int j=1; j<=m; j++)
  48.         {
  49.             fout<<a[i][j]<<" ";
  50.         }
  51.         fout<<endl;
  52.     }
  53.  
  54.     s.push({n,m});
  55.  
  56.     int stopi, stopj;
  57.     stopi=n;
  58.     stopj=m;
  59.     int i=n, j=m;
  60.  
  61.     while(i!=1 || j!=1)
  62.     {
  63.         a[i][j]-=max(a[i][j-1],a[i-1][j]);
  64.         if(a[i][j-1]>a[i-1][j])
  65.         {
  66.             s.push({i,j-1});
  67.             j--;
  68.         }
  69.         else
  70.         {
  71.             s.push({i-1,j});
  72.             i--;
  73.         }
  74.     }
  75.  
  76.     while(!s.empty())
  77.     {
  78.         fout<<s.top().first<<" "<<s.top().second<<endl;
  79.         s.pop();
  80.     }
  81.  
  82.     fin.close();
  83.     fout.close();
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment