Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- int mat[905][905];
- int v[1805];
- int dp[1805][2][2];
- int dp2[1805][2];
- void recon ()
- {
- }
- int main()
- {
- freopen("flori2.in","r",stdin);
- freopen("flori2.out","w",stdout);
- int n,m;
- scanf("%d %d",&n,&m);
- for(int i=1;i<=n;++i)
- {
- for(int j=1;j<=m;++j)
- {
- scanf("%d",&mat[i][j]);
- mat[i][j]+=mat[i-1][j-1];
- }
- }
- int cnt=0,pos=0;
- int maxx;
- for(int i=1;i<=n;++i)
- {
- v[++cnt]=mat[i][m];
- }
- for(int i=m-1;i>=1;--i)
- {
- v[++cnt]=mat[n][i];
- }
- ///@l3x
- for(int i=1;i<=cnt;++i)
- {
- for(int j=0;j<=1;++j)
- {
- maxx=0;
- for(int k=1;k<i;++k)
- {
- if(v[k]<=v[i])
- {
- if(dp[k][1][0]>maxx)
- {
- maxx=dp[k][1][0];
- pos=k;
- }
- }
- }
- dp[i][j][0]=maxx+v[i]*j;
- dp[i][j][1]=pos;
- }
- }
- ///R@r3$
- for(int i=cnt;i>=1;i--)
- {
- maxx=0;
- for(int k=1;k<=cnt;k++)
- {
- if(v[k]<v[i]&&(k!=i))
- {
- if(dp[k][1][0]>maxx)
- {
- maxx=dp[k][1][0];
- pos=k;
- }
- }
- }
- for(int k=cnt;k>i;--k)
- {
- if(v[k]<v[i])
- {
- if(maxx<dp2[k][0])
- {
- maxx=dp2[k][0];
- pos=k;
- }
- }
- }
- dp2[i][0]=maxx+v[i];
- dp2[i][1]=pos;
- }
- maxx=0;
- for(int i=1;i<=cnt;++i)
- {
- if(dp2[i][0]>maxx)
- {
- maxx=dp2[i][0];
- pos=i;
- }
- }
- printf("%d\n",maxx);
- /*
- while (pos != 0)
- {
- printf("%d ", pos) ;
- pos = dp2[pos][1] ;
- }*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement