Submission #617756


Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int h, w;
long long x[55][55];
long long y[55][55];

long long dp[55][55][55][55], maxn = -1000000000000000LL;

int main() {
	memset(dp, 0, sizeof(dp));
	cin >> h >> w;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> x[i][j];
			y[i][j] = y[i][j - 1] + x[i][j];
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			dp[i][j][i][j] = x[i][j];
			for (int k = i; k <= h; k++) {
				for (int l = j; l <= w; l++) {
					dp[i][j][k][l] = max(dp[i][j][k - 1][l] + (y[k][l] - y[k][j - 1]), x[k][l]);
				}
			}
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			for (int k = i; k <= w; k++){
				for (int l = j; l <= w; l++) {
					if (k != i && l != j) {
						dp[i][j][k][l] = max(dp[i][j][k][l], max(dp[i][j][k - 1][l], dp[i][j][k][l - 1]));
					}
					else if (k != i) {
						dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l]);
					}
					else if (l != j) {
						dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1]);
					}
				}
			}
		}
	}
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++) {
			for (int k = 1; k <= h; k++) {
				for (int l = 1; l <= w; l++) {
					if (i < k || j < l) {
						maxn = max(maxn, dp[1][1][i][j] + dp[k][l][h][w]);
					}
				}
			}
		}
	}
	cout << maxn << endl;
	return 0;
}

Submission Info

Submission Time
Task D - 庭園
User E869120
Language C++ (GCC 4.9.2)
Score 0
Code Size 1441 Byte
Status WA
Exec Time 451 ms
Memory 72284 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 50 0 / 50
Status
AC × 4
AC × 6
WA × 9
AC × 6
WA × 17
RE × 7
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask1 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 163 ms 72228 KB
sample1.txt AC 171 ms 72224 KB
sample2.txt AC 172 ms 72180 KB
sample3.txt AC 170 ms 72228 KB
subtask0_0.txt WA 235 ms 72228 KB
subtask0_1.txt WA 243 ms 72232 KB
subtask0_10.txt WA 254 ms 72224 KB
subtask0_11.txt WA 227 ms 72220 KB
subtask0_12.txt AC 245 ms 72232 KB
subtask0_13.txt WA 236 ms 72228 KB
subtask0_14.txt AC 225 ms 72224 KB
subtask0_2.txt AC 217 ms 72284 KB
subtask0_3.txt WA 225 ms 72220 KB
subtask0_4.txt AC 239 ms 72224 KB
subtask0_5.txt WA 244 ms 72228 KB
subtask0_6.txt WA 241 ms 72236 KB
subtask0_7.txt AC 244 ms 72232 KB
subtask0_8.txt WA 221 ms 72228 KB
subtask0_9.txt AC 249 ms 72236 KB
subtask1_0.txt RE 443 ms 72224 KB
subtask1_1.txt RE 441 ms 72228 KB
subtask1_10.txt RE 440 ms 72224 KB
subtask1_11.txt WA 183 ms 72236 KB
subtask1_12.txt RE 416 ms 72224 KB
subtask1_13.txt WA 180 ms 72228 KB
subtask1_14.txt WA 179 ms 72232 KB
subtask1_2.txt RE 451 ms 72224 KB
subtask1_3.txt WA 179 ms 72224 KB
subtask1_4.txt WA 165 ms 72216 KB
subtask1_5.txt WA 172 ms 72224 KB
subtask1_6.txt WA 173 ms 72284 KB
subtask1_7.txt RE 441 ms 72236 KB
subtask1_8.txt RE 439 ms 72232 KB
subtask1_9.txt WA 179 ms 72228 KB