제출 #9713

#제출 시각아이디문제언어결과실행 시간메모리
9713coreaOn grid (kriii2_O)C++14
4 / 4
184 ms225880 KiB
#include <cstdio> #include <iostream> #include <cstring> #include <tuple> #include <cassert> #include <vector> #include <algorithm> using namespace std; #define REP(i, n) for(int i=0; i < n; ++i) int n, m; int a[305][305]; long long S[305][305]; long long V[305][305]; long long C[305][305]; long long M[305][305][305]; long long compute_M(int i, int j, int k) { if(j == 1) { int l = 0; return C[k][l] - S[i][l] - S[k][j] + S[k][l]; } else { long long left = M[i][j - 1][k] - S[k][j] + S[k][j - 1]; int l = j - 1; long long right = C[k][l] - S[i][l] - S[k][j] + S[k][l]; return max(left, right); } } long long go() { memset(C, 0, sizeof(C)); memset(M, 0, sizeof(M)); memset(V, 0, sizeof(V)); for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= m; ++ j) { S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]; } } const long long INF = 1LL << 50; for(int i = 1; i <= n; ++ i) { V[i][0] = -INF; C[i][0] = -INF; } for(int j = 1; j <= m; ++ j) { V[0][j] = -INF; C[0][j] = -INF; } for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= m; ++ j) { // M[i][j] = max { C[k][l] - S[i][l] - S[k][j] + S[k][] } // k < i, l < j // M[i][j-1] = max { C[k][l] - S[i][l] - S[k][j] + S[k][l] } // k < i, l < j-1 long long maxi = 0; for(int k = 0; k < i; ++ k) { M[i][j][k] = compute_M(i, j, k); // printf("M %d %d %d = %lld\n", i, j, k, M[i][j][k]); maxi = max(maxi, M[i][j][k]); } C[i][j] = maxi + S[i][j]; /* V[i][j] = -INF; for(int k = 0; k < i; ++ k) { for(int l = 0; l < j; ++ l) { V[i][j] = max(V[i][j], V[k][l] - S[i][l] - S[k][j] + S[k][l] + S[i][j]); } } */ // printf("[%3lld]<%3lld> / %2lld+%2lld ", C[i][j], V[i][j], S[i][j], maxi); } // printf("\n"); } return C[n][m]; } int main() { while(cin >> n >> m && n && m ) { for(int i = 1; i <= n; ++ i) { for(int j=1; j<=m; ++j) { cin >> a[i][j]; } } cout << go() << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...