QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290556#6781. 书法家MoRanSky100 ✓257ms6280kbC++232.6kb2023-12-25 05:49:012023-12-25 05:49:02

Judging History

你现在查看的是最新测评结果

  • [2023-12-25 05:49:02]
  • 评测
  • 测评结果:100
  • 用时:257ms
  • 内存:6280kb
  • [2023-12-25 05:49:01]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 155, M = 505, INF = 2e9;

int n, m, a[N][M], f[11][N][N], g[11][N][N], s[N], gx[N], ans;

void inline wk() {
	ans = -INF;
	memset(f, 0xcf, sizeof f);
	for (int i = 1; i <= m; i++) {
		memcpy(g, f, sizeof f);
		memset(f, 0xcf, sizeof f);
		for (int j = 1; j <= n; j++) s[j] = s[j - 1] + a[j][i];
		for (int k = 0; k < 11; k++) {
			for (int x = 1; x <= n; x++) {
				for (int y = x; y <= n; y++) {
					if (k == 3) {
						chkMax(f[k][1][1], g[k - 1][x][y]);
					} else if (k == 7) {
						chkMax(f[k][1][1], g[k - 1][x][y]);
					}
					if (((k <= 6 && k >= 4) || (k <= 10 && k >= 8)) && y - x + 1 < 3) continue;
					int w = s[y] - s[x - 1];
					if (k == 5 || k == 8 || k == 10) w = a[x][i] + a[y][i];
					if (k == 7 || k == 3) w = 0;
					if (k != 4 && k != 6) chkMax(f[k][x][y], g[k][x][y] + w);
					if (k == 0) chkMax(f[k][x][y], w);
					if (k == 4 || k == 8) {
						chkMax(f[k][x][y], g[k - 1][1][1] + w);
					}
					if (k == 5 || k == 6 || k == 9 || k == 10) {
						chkMax(f[k][x][y], g[k - 1][x][y] + w);
					}
				}
			}
		}	
		
		// 0 -> 1
		for (int y = 1; y <= n; y++) {
			int v = -INF;
			for (int x = 1; x <= y; x++) {
				chkMax(f[1][x][y], v + s[y] - s[x - 1]);
				chkMax(v, g[0][x][y]);
			}
		}

		// 1 -> 2
		for (int x = 1; x <= n; x++) {
			int v = -INF;
			for (int y = x; y <= n; y++) {
				chkMax(f[2][x][y], v + s[y] - s[x - 1]);
				chkMax(v, g[1][x][y]);
			}
		}

		// 1 -> 1
		memset(gx, 0xcf, sizeof gx);
		for (int x = n; x; x--) {
			int v = -INF;
			for (int y = n; y >= x - 1; y--) {
				chkMax(v, g[1][x][y]);
				chkMax(gx[y], v);
				if (x <= y) chkMax(f[1][x][y], gx[y] + s[y] - s[x - 1]);
			}
		}

		

		for (int x = 1; x <= n; x++) 
			for (int y = x; y <= n; y++)
				chkMax(ans, f[10][x][y]);
	}
}

int main() {
	read(n), read(m);
    for (int i = 1; i <= n; i++)
    	for (int j = 1; j <= m; j++) read(a[n - i + 1][j]);
    wk();
	printf("%d\n", ans);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 0ms
memory: 5992kb

input:

3 12
1 -1 1 1 0 0 0 0 -1 0 -1 1
1 1 1 0 1 0 0 1 -1 1 0 0
-1 1 -1 -1 0 0 1 -1 -1 1 0 -1

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 5
Accepted
time: 2ms
memory: 5868kb

input:

3 12
7 32 39 -20 -6 9 -32 17 30 28 13 14
37 -36 -37 -13 29 -42 20 -20 38 -21 13 5
-29 -42 33 10 -28 13 27 30 5 39 9 -6

output:

161

result:

ok 1 number(s): "161"

Test #3:

score: 5
Accepted
time: 2ms
memory: 5852kb

input:

3 12
-40 26 12 38 -22 36 46 -9 35 -29 37 -34
-4 23 13 5 7 -27 34 50 42 -20 -32 6
42 43 -18 19 -4 37 -9 -25 36 42 10 33

output:

322

result:

ok 1 number(s): "322"

Test #4:

score: 5
Accepted
time: 2ms
memory: 5816kb

input:

3 12
-5 -44 -5 -10 36 -42 39 10 -10 41 34 5
-25 2 -49 -41 -20 -1 34 -26 30 -46 -5 -37
-25 -31 -38 15 -47 -16 20 8 5 -39 -15 -47

output:

-124

result:

ok 1 number(s): "-124"

Test #5:

score: 5
Accepted
time: 0ms
memory: 5864kb

input:

10 19
-31 -17 0 -18 41 27 -3 -9 -29 18 -9 -5 -8 17 39 31 32 12 32
41 35 2 38 16 14 21 34 22 13 -21 32 -16 40 8 16 -23 -22 23
29 -6 27 30 35 -23 -7 -27 -3 -35 3 -5 -4 19 40 -36 20 11 -21
9 3 -20 49 26 33 32 28 27 42 40 -10 -3 44 -32 -35 2 27 -31
8 -38 13 12 -20 8 21 2 5 47 26 -18 38 46 35 -6 -26 39 -...

output:

1730

result:

ok 1 number(s): "1730"

Test #6:

score: 5
Accepted
time: 3ms
memory: 5880kb

input:

9 20
1 -26 -27 31 -41 30 35 -14 35 -14 -4 28 23 -21 27 34 -38 26 31 -42
-41 38 -9 -50 27 27 -35 40 33 0 31 -18 -6 -30 -32 -19 -29 -4 12 40
-38 -2 -7 -27 -25 2 -41 10 6 -18 -33 8 -29 27 23 -38 -43 1 -39 -15
28 40 25 -3 -14 -32 7 -24 -19 -25 -12 28 16 39 -39 -47 20 35 -2 35
-24 37 -1 -4 27 -47 -29 -44...

output:

652

result:

ok 1 number(s): "652"

Test #7:

score: 5
Accepted
time: 2ms
memory: 5884kb

input:

10 20
37 1 22 45 -3 23 23 17 46 23 34 4 47 18 -2 0 25 17 41 43
34 37 34 12 22 8 5 35 17 50 43 22 38 45 15 21 11 33 26 15
34 32 39 42 34 35 0 15 12 -4 15 12 7 26 6 49 -3 17 8 43
19 31 45 35 36 31 34 32 23 26 38 9 28 33 30 28 43 20 3 2
45 23 -1 24 41 47 35 24 9 33 19 46 34 11 24 12 0 25 46 30
47 50 36...

output:

3905

result:

ok 1 number(s): "3905"

Test #8:

score: 5
Accepted
time: 0ms
memory: 5948kb

input:

10 20
-14 -49 -38 -10 -26 -28 -35 -48 -31 -12 4 -10 -39 -34 -17 -47 -15 -27 -46 -25
-17 -7 -19 -48 -19 -43 -3 -6 -14 -33 2 -43 -10 -44 -40 -40 -15 -7 -10 -37
-28 -22 -7 -46 -3 -25 -30 -32 -8 -6 -4 -38 -7 -14 -49 -16 -37 3 -16 -40
-27 -36 -18 -21 -41 -40 -34 -43 -39 -19 -24 -15 -12 -32 -24 -46 -9 -17...

output:

-174

result:

ok 1 number(s): "-174"

Test #9:

score: 5
Accepted
time: 186ms
memory: 6124kb

input:

139 486
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

66863

result:

ok 1 number(s): "66863"

Test #10:

score: 5
Accepted
time: 201ms
memory: 6060kb

input:

146 477
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

68916

result:

ok 1 number(s): "68916"

Test #11:

score: 5
Accepted
time: 18ms
memory: 6020kb

input:

80 80
-84 -158 -1 157 -182 -49 -171 47 -10 -127 71 199 -26 -188 -69 29 107 199 -189 154 -195 -184 131 -148 192 -198 2 -198 -193 -9 -82 -81 -93 124 -149 -60 102 -34 -149 -109 68 70 198 6 133 -144 197 155 -78 -192 179 -35 -54 -18 -81 3 -94 23 -125 -27 34 -190 -110 -5 -166 -153 166 -177 -44 -23 195 -10...

output:

44814

result:

ok 1 number(s): "44814"

Test #12:

score: 5
Accepted
time: 15ms
memory: 5968kb

input:

80 80
54 68 8 -16 42 37 -167 -5 -87 33 -77 -176 -54 118 -33 11 -26 -178 -174 -63 52 54 89 -166 -167 -80 -43 -92 -181 -174 57 -177 -195 -83 -38 14 -52 158 -199 -9 82 -133 -148 -56 55 143 73 29 -103 -108 -124 -189 174 -129 -200 14 14 -74 -159 -79 127 142 -165 77 -168 -138 130 -2 156 -21 61 68 -31 80 3...

output:

29074

result:

ok 1 number(s): "29074"

Test #13:

score: 5
Accepted
time: 14ms
memory: 6152kb

input:

80 80
-162 -56 -21 -40 62 -71 -69 140 159 -121 67 134 -144 90 50 58 130 60 7 -129 -94 140 188 -105 22 134 60 -143 -143 166 174 30 91 163 91 -76 149 183 56 1 108 -33 -20 118 -162 56 74 199 -84 67 44 194 138 -28 -3 166 -91 13 184 -167 -82 131 0 -189 174 170 147 -150 155 6 -139 -163 33 -100 35 -161 40 ...

output:

56131

result:

ok 1 number(s): "56131"

Test #14:

score: 5
Accepted
time: 16ms
memory: 5956kb

input:

78 75
-61 -86 -168 -62 -116 -79 -103 -53 -58 -139 -176 -29 -7 -88 -120 -1 -139 -7 -107 -56 -98 -27 -181 -127 -112 -133 -134 -10 -47 -179 -97 -129 -5 -189 -56 -115 -106 -3 -42 -172 -103 -186 -162 -33 -184 0 -41 -103 -69 -51 -9 -112 -3 -55 -128 -79 -44 -80 -121 -187 -197 -93 -116 -144 -159 -132 -115 -...

output:

-475

result:

ok 1 number(s): "-475"

Test #15:

score: 5
Accepted
time: 115ms
memory: 6020kb

input:

100 400
-1 -47 -56 164 -38 92 71 -140 49 -64 144 111 154 7 -47 -63 60 -153 -174 -160 -79 68 -1 -160 104 -126 87 -42 109 188 -100 173 127 39 -145 -119 -45 -188 -13 -180 138 97 106 100 -104 -35 -42 199 190 -56 -24 -188 138 -24 182 -128 150 -67 -100 -99 -125 -127 9 -41 -92 -10 170 -87 119 -101 176 -76 ...

output:

124482

result:

ok 1 number(s): "124482"

Test #16:

score: 5
Accepted
time: 253ms
memory: 6224kb

input:

150 500
117 -39 155 -88 -180 107 -6 -8 41 -156 2 -193 -93 -165 -25 -89 -130 54 91 -72 136 175 7 -40 38 93 -44 164 112 123 51 103 119 -190 31 18 170 -163 -118 -25 74 -113 -186 -164 -78 -26 -93 105 -25 23 -110 170 -85 -126 139 117 85 174 115 -64 161 -62 -81 -33 -183 -113 84 -58 -123 -161 -107 17 118 -...

output:

81570

result:

ok 1 number(s): "81570"

Test #17:

score: 5
Accepted
time: 254ms
memory: 6140kb

input:

150 500
-7 -144 -132 38 -180 -2 -82 85 149 -56 87 -96 -149 -37 -147 -179 -36 121 5 -129 67 -106 -172 37 -21 41 -17 -149 4 -146 -75 -124 -89 -64 23 -74 33 -89 -157 -30 92 -46 86 -95 -33 80 -85 -128 105 -14 -8 47 -112 -132 -31 -74 10 -149 -124 19 -159 -25 -57 -142 -93 157 29 -152 -32 -166 61 -69 98 -3...

output:

52564

result:

ok 1 number(s): "52564"

Test #18:

score: 5
Accepted
time: 257ms
memory: 6164kb

input:

150 500
-198 143 181 64 76 106 187 -79 200 45 -43 92 49 -71 -35 -78 153 -75 183 -37 -35 -38 -71 129 110 -37 -151 -150 -116 -87 118 149 -103 -65 -169 126 -52 194 -141 148 1 43 -169 52 -53 59 65 178 -87 139 -189 31 77 -5 -195 -11 64 151 -130 50 -94 125 -83 74 -133 194 -91 -39 177 54 -114 176 -31 77 16...

output:

155398

result:

ok 1 number(s): "155398"

Test #19:

score: 5
Accepted
time: 251ms
memory: 6280kb

input:

150 500
50 -123 42 118 -7 -123 -66 -136 55 -97 28 129 -86 -92 -34 121 104 -39 4 29 -31 50 -36 127 108 -56 -4 -132 -50 -31 -62 147 73 -36 140 -55 -92 22 -40 -127 -34 25 -1 -105 -55 -118 85 83 -42 -144 139 14 9 -132 115 126 -38 -3 0 -80 -101 3 100 46 -38 62 -83 81 -59 -96 36 127 60 -78 128 44 -143 51 ...

output:

129601

result:

ok 1 number(s): "129601"

Test #20:

score: 5
Accepted
time: 254ms
memory: 6100kb

input:

150 500
-1 1 -2 0 0 -1 2 -2 -2 -2 -1 -1 -1 -2 -1 1 0 -1 -1 0 1 -2 2 2 -2 -2 2 -1 2 1 0 0 1 0 1 -1 -2 2 2 -2 -2 0 -2 1 -2 -2 2 2 1 0 -1 2 -2 1 -2 -2 -1 -2 1 -1 0 -2 1 2 1 1 -2 0 1 -1 -2 0 -1 -1 2 2 0 2 2 -2 1 1 1 2 1 2 2 -1 0 1 2 2 1 1 0 0 0 -2 2 -2 -2 -1 2 -2 2 -2 2 2 1 0 -2 0 1 2 -1 -1 -1 0 0 0 -2 ...

output:

2000

result:

ok 1 number(s): "2000"

Extra Test:

score: 0
Extra Test Passed