Advertisement
haufont

Untitled

Jul 23rd, 2016
347
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.92 KB | None | 0 0
  1. #include<iostream>
  2. #include<string>
  3. #include<map>
  4. #include<algorithm>
  5. using namespace std;
  6. long long S[1515][1515];
  7. long long D[1515][1515];
  8. int main()
  9. {
  10. int n,m;
  11. cin>>n>>m;
  12. int y;
  13. memset(S,0,sizeof(S));
  14. memset(D,0,sizeof(D));
  15. for(int i=1;i<=n;i++)
  16. {
  17. for(int v=1;v<=m;v++)
  18. {
  19. cin>>y;
  20. S[i][v]=S[i][v-1]+y;
  21. }
  22. }
  23. for(int i=1;i<=n;i++)
  24. {
  25. int max1=-1000000;
  26. if(i%2==1)
  27. {
  28. for(int v=m;v>=2;v--)
  29. {
  30. D[i][v]=D[i-1][v-1]+S[i][v];
  31. if(D[i][v]>max1)
  32. {
  33. max1=D[i][v];
  34. }
  35. else
  36. {
  37. D[i][v]=max1;
  38. }
  39. }
  40. }
  41. if(i%2==0)
  42. {
  43. for(int v=1;v<=m-1;v++)
  44. {
  45. D[i][v]=D[i-1][v+1]+S[i][v];
  46. if(D[i][v]>max1)
  47. {
  48. max1=D[i][v];
  49. }
  50. else
  51. {
  52. D[i][v]=max1;
  53. }
  54. }
  55. }
  56. }
  57. if(n==1)
  58. {
  59. cout<<max(S[1][1],D[n][2]);
  60. return 0;
  61. }
  62. if(n%2==0)
  63. {
  64. cout<<D[n][m-1];
  65. }
  66. else
  67. {
  68. cout<<D[n][2];
  69. }
  70.  
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement