Advertisement
Guest User

Untitled

a guest
Mar 25th, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.04 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. int mat[905][905];
  3. int v[1805];
  4. int dp[1805][2][2];
  5. int dp2[1805][2];
  6. void recon ()
  7. {
  8.  
  9. }
  10. int main()
  11. {
  12.     freopen("flori2.in","r",stdin);
  13.     freopen("flori2.out","w",stdout);
  14.     int n,m;
  15.     scanf("%d %d",&n,&m);
  16.     for(int i=1;i<=n;++i)
  17.     {
  18.         for(int j=1;j<=m;++j)
  19.         {
  20.             scanf("%d",&mat[i][j]);
  21.             mat[i][j]+=mat[i-1][j-1];
  22.         }
  23.     }
  24.     int cnt=0,pos=0;
  25.     int maxx;
  26.     for(int i=1;i<=n;++i)
  27.     {
  28.         v[++cnt]=mat[i][m];
  29.     }
  30.     for(int i=m-1;i>=1;--i)
  31.     {
  32.         v[++cnt]=mat[n][i];
  33.     }
  34.     ///@l3x
  35.     for(int i=1;i<=cnt;++i)
  36.     {
  37.         for(int j=0;j<=1;++j)
  38.         {
  39.             maxx=0;
  40.             for(int k=1;k<i;++k)
  41.             {
  42.                 if(v[k]<=v[i])
  43.                 {
  44.                     if(dp[k][1][0]>maxx)
  45.                     {
  46.                         maxx=dp[k][1][0];
  47.                         pos=k;
  48.                     }
  49.                 }
  50.             }
  51.             dp[i][j][0]=maxx+v[i]*j;
  52.             dp[i][j][1]=pos;
  53.         }
  54.     }
  55.     ///R@r3$
  56.     for(int i=cnt;i>=1;i--)
  57.     {
  58.         maxx=0;
  59.         for(int k=1;k<=cnt;k++)
  60.         {
  61.             if(v[k]<v[i]&&(k!=i))
  62.             {
  63.                 if(dp[k][1][0]>maxx)
  64.                     {
  65.                         maxx=dp[k][1][0];
  66.                         pos=k;
  67.                     }
  68.             }
  69.         }
  70.         for(int k=cnt;k>i;--k)
  71.         {
  72.             if(v[k]<v[i])
  73.             {
  74.                 if(maxx<dp2[k][0])
  75.                     {
  76.                         maxx=dp2[k][0];
  77.                         pos=k;
  78.                     }
  79.             }
  80.  
  81.         }
  82.         dp2[i][0]=maxx+v[i];
  83.         dp2[i][1]=pos;
  84.     }
  85.     maxx=0;
  86.     for(int i=1;i<=cnt;++i)
  87.     {
  88.         if(dp2[i][0]>maxx)
  89.             {
  90.                 maxx=dp2[i][0];
  91.                 pos=i;
  92.             }
  93.     }
  94.     printf("%d\n",maxx);
  95.     /*
  96.     while (pos != 0)
  97.     {
  98.         printf("%d ", pos) ;
  99.         pos = dp2[pos][1] ;
  100.     }*/
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement