QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290556 | #6781. 书法家 | MoRanSky | 100 ✓ | 257ms | 6280kb | C++23 | 2.6kb | 2023-12-25 05:49:01 | 2023-12-25 05:49:02 |
Judging History
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