Submission #9313

#TimeUsernameProblemLanguageResultExecution timeMemory
9313lemonsqueezeOn grid (kriii2_O)C++98
4 / 4
464 ms216972 KiB
#include <stdio.h> #include <algorithm> using namespace std; int n, m; long long a[301][301]; long long s[301][301]; long long d[301][301]; long long w[301][301][302]; int main () { scanf ("%d%d", &n, &m); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { scanf ("%lld", &a[i][j]); s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]; } for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { d[i][j] = s[i][j]; if (j>=2) { for (int a=1; a<i; a++) { if (d[i][j] < w[a][i][j] + s[i][j] - s[a][j]) d[i][j] = w[a][i][j] + s[i][j] - s[a][j]; } for (int a=1; a<i; a++) w[a][i][j+1] = max (w[a][i][j], d[a][j] + s[a][j] - s[i][j]); } else { for (int a=1; a<i; a++) w[a][i][j+1] = d[a][j] + s[a][j] - s[i][j]; } } } printf ("%lld\n", d[n][m]); return 0; } /* 2 2 1 -1 -1 1 5 5 4 -2 3 -4 2 -2 1 1 4 -2 -3 1 -1 2 5 2 -4 2 3 5 1 -4 4 -1 -2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...