Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string>
- #include<map>
- #include<algorithm>
- using namespace std;
- long long S[1515][1515];
- long long D[1515][1515];
- int main()
- {
- int n,m;
- cin>>n>>m;
- int y;
- memset(S,0,sizeof(S));
- memset(D,0,sizeof(D));
- for(int i=1;i<=n;i++)
- {
- for(int v=1;v<=m;v++)
- {
- cin>>y;
- S[i][v]=S[i][v-1]+y;
- }
- }
- for(int i=1;i<=n;i++)
- {
- int max1=-1000000;
- if(i%2==1)
- {
- for(int v=m;v>=2;v--)
- {
- D[i][v]=D[i-1][v-1]+S[i][v];
- if(D[i][v]>max1)
- {
- max1=D[i][v];
- }
- else
- {
- D[i][v]=max1;
- }
- }
- }
- if(i%2==0)
- {
- for(int v=1;v<=m-1;v++)
- {
- D[i][v]=D[i-1][v+1]+S[i][v];
- if(D[i][v]>max1)
- {
- max1=D[i][v];
- }
- else
- {
- D[i][v]=max1;
- }
- }
- }
- }
- if(n==1)
- {
- cout<<max(S[1][1],D[n][2]);
- return 0;
- }
- if(n%2==0)
- {
- cout<<D[n][m-1];
- }
- else
- {
- cout<<D[n][2];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement