QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #210396 | #3687. Boss 单挑战 | 10circle | 100 ✓ | 114ms | 11308kb | C++14 | 2.3kb | 2023-10-11 13:34:28 | 2023-10-11 13:34:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
ll read() {
ll a = 0, b = 0; char c = getchar();
while (c < '0' || c > '9') b ^= (c == '-'), c = getchar();
while (c >= '0' && c <= '9') a = a * 10 - 48 + c, c = getchar();
return b ? -a : a;
}
const int N = 1005;
int n, m, hp, mp, sp, dh, dm, ds, X, a[N], n1, n2, b[10], c[10], y[10], z[10];
int f[N][N], g[N][N];
int cf[N], cg[N];
void calc(int m, int b[], int y[], int x, int f[N][N], int mp, int dm, int cf[N]) {
for (int i = 1; i <= n; ++i) {
memset(f[i], 0, mp + 1 << 2);
for (int j = 0; j <= mp; ++j) {
f[i][j] = max(f[i][j], f[i - 1][max(0, j - dm)] + x);
for (int k = 0; k < m; ++k) if (j + b[k] <= mp) {
f[i][j] = max(f[i][j], f[i - 1][j + b[k]] + y[k]);
}
}
for (int j = mp; j; --j) f[i][j - 1] = max(f[i][j - 1], f[i][j]);
cf[i] = f[i][0];
}
}
bool chk(int num) {
for (int i = 0; i <= num; ++i) if (cf[i] + cg[num - i] >= m) return 1;
return 0;
}
void sol() {
n = read(), m = read(), hp = read(), mp = read(), sp = read(), dh = read(), dm = read(), ds = read(), X = read();
for (int i = 1; i <= n; ++i) a[i] = read();
n1 = read(); for (int i = 0; i < n1; ++i) b[i] = read(), y[i] = read();
n2 = read(); for (int i = 0; i < n2; ++i) c[i] = read(), z[i] = read();
calc(n1, b, y, 0, f, mp, dm, cf);
calc(n2, c, z, X, g, sp, ds, cg);
// for (int i = 0; i <= n; ++i) cerr << cf[i] << ' '; cerr << endl;
// for (int i = 0; i <= n; ++i) cerr << cg[i] << ' '; cerr << endl;
for (int k = 1; k <= n + 1; ++k) {
int nu = k;
static int h[N], d[N];
h[0] = hp;
for (int i = 1; i < k; ++i) d[i] = 0;
vint hv;
for (int i = 1; i < k; ++i) {
h[i] = min(hp, h[i - 1] + d[i] - a[i]);
hv.push_back(i);
while (h[i] <= 0) {
if (!hv.size()) { cout << "No" << '\n'; return; }
int u = hv.back(); hv.pop_back();
d[u] += dh;
for (int t = u; t <= i; ++t) h[t] = min(hp, h[t - 1] + d[t]) - a[t];
}
//for (int j = 1; j <= i; ++j) cerr << h[j] << ' '; cerr << ": " << i << ' ' << k << endl;
}
//for (int i : hv) cerr << i << ' '; cerr << " : " << k << endl;
if (k <= n && chk(hv.size() + 1)) {
cout << "Yes " << k << '\n';
return;
}
}
cout << "Tie" << '\n';
}
int main() {
int T = read();
while (T--) sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 5556kb
input:
10 9 166 57 61 58 46 36 30 49 36 34 25 25 39 20 31 56 38 0 0 9 109 67 63 66 33 37 32 59 35 36 66 24 28 26 27 39 66 0 0 6 135 64 56 63 47 41 42 59 63 63 25 24 29 38 0 0 9 132 54 52 63 43 37 34 52 26 21 35 26 21 35 20 34 23 0 0 6 129 69 68 50 33 47 41 48 34 68 34 35 68 28 0 0 7 122 66 52 66 37 38 40 5...
output:
Yes 8 Yes 2 No Yes 3 No Yes 3 Tie Tie Tie Tie
result:
ok 10 lines
Test #2:
score: 10
Accepted
time: 1ms
memory: 5500kb
input:
10 10 121 64 54 51 41 34 42 51 14 19 29 63 24 24 12 18 16 28 1 41 65 1 3 76 9 220 65 65 52 43 47 42 31 29 18 20 64 25 26 60 24 18 1 23 91 1 10 64 9 189 63 51 60 48 37 44 53 25 27 11 27 22 15 24 22 10 1 44 95 1 56 65 10 296 52 62 57 49 35 37 54 51 15 11 25 51 26 51 18 12 27 1 9 77 1 57 82 7 255 69 55...
output:
Yes 2 Yes 3 Yes 3 Yes 10 Yes 6 Yes 2 Tie Tie No Yes 2
result:
ok 10 lines
Test #3:
score: 10
Accepted
time: 1ms
memory: 5520kb
input:
10 6 1010 55 54 69 49 31 44 54 22 14 11 28 25 18 1 15 349 1 34 343 7 1159 60 54 52 32 31 46 59 59 25 29 10 29 25 59 1 21 353 1 49 393 8 1029 62 55 64 35 41 34 41 15 14 21 24 24 26 16 17 1 48 342 1 24 398 9 1125 63 67 59 47 40 40 36 23 10 19 28 12 13 29 15 60 1 7 383 1 6 391 10 1095 67 69 60 35 32 39...
output:
Yes 3 Tie Yes 3 Yes 3 No No Yes 8 Tie Yes 6 Yes 3
result:
ok 10 lines
Test #4:
score: 10
Accepted
time: 1ms
memory: 5596kb
input:
10 14 1121 62 52 52 41 45 30 35 24 18 25 26 13 61 11 10 15 29 18 14 17 20 6 7 160 46 163 36 180 28 133 18 150 35 104 9 14 134 23 110 39 126 45 151 33 108 51 189 5 186 9 129 17 186 19 1133 55 61 69 40 31 49 33 54 20 54 13 28 24 15 21 10 25 54 10 22 20 24 54 15 54 54 10 23 192 49 114 27 164 44 135 24 ...
output:
Yes 13 No Yes 12 No Yes 8 Tie Yes 11 Tie Yes 16 No
result:
ok 10 lines
Test #5:
score: 10
Accepted
time: 0ms
memory: 9592kb
input:
10 89 7449 56 53 69 31 42 49 48 45 19 14 14 16 12 15 49 44 17 46 19 19 11 19 46 19 11 19 44 17 19 16 17 46 12 17 13 17 16 11 18 14 16 13 19 17 17 14 40 19 45 14 14 17 14 12 14 13 44 14 16 18 12 45 11 16 10 17 15 17 13 17 11 49 19 46 10 17 19 48 41 10 11 12 42 15 48 44 10 10 15 11 18 17 40 10 15 17 7...
output:
No Yes 60 Yes 70 Yes 61 Yes 49 No Yes 40 Tie No Yes 42
result:
ok 10 lines
Test #6:
score: 10
Accepted
time: 0ms
memory: 5856kb
input:
10 85 9085 69 52 68 46 40 39 52 19 13 46 12 11 16 46 10 18 10 19 15 12 15 17 40 46 18 16 44 15 19 16 10 14 13 14 13 19 14 10 17 18 16 45 13 19 13 17 12 10 18 17 41 19 16 46 16 19 17 16 13 12 42 11 16 19 18 16 18 13 17 16 13 18 15 49 14 42 12 42 15 11 40 19 18 41 11 14 41 13 16 13 11 17 7 47 266 16 2...
output:
Yes 58 Yes 66 Yes 38 Yes 53 Yes 70 No Yes 58 Yes 49 Tie Yes 60
result:
ok 10 lines
Test #7:
score: 10
Accepted
time: 31ms
memory: 6844kb
input:
10 263 412733 507 593 898 356 410 484 209 19 44 11 10 19 14 10 14 45 17 13 13 15 10 14 11 16 16 14 11 19 41 41 11 43 12 16 13 16 16 10 10 12 15 47 14 19 13 17 14 12 12 19 40 10 44 10 13 16 45 12 16 19 13 12 13 18 11 15 15 16 49 13 12 10 47 40 15 17 15 14 15 11 19 44 44 13 40 44 18 14 10 13 19 17 17 ...
output:
Yes 164 Yes 174 Yes 205 Tie Yes 221 Tie Tie Yes 241 Yes 182 Yes 198
result:
ok 10 lines
Test #8:
score: 10
Accepted
time: 85ms
memory: 11244kb
input:
10 958 273224 685 873 591 381 492 477 491 493 150 172 440 134 175 132 478 191 458 112 465 464 182 185 184 176 411 404 493 191 169 155 180 172 444 108 114 128 199 165 135 157 153 130 156 451 418 159 482 138 124 107 402 174 127 181 130 174 164 147 431 166 459 126 109 146 165 112 100 124 163 178 183 43...
output:
Yes 919 Tie Yes 704 Yes 553 Yes 814 Tie Tie Yes 654 No No
result:
ok 10 lines
Test #9:
score: 10
Accepted
time: 109ms
memory: 11304kb
input:
10 946 479137 951 805 988 206 466 371 475 151 111 195 174 114 164 186 190 132 191 175 104 121 160 191 112 118 190 102 116 185 115 199 153 177 192 159 148 135 186 131 166 181 102 141 188 135 163 147 164 101 134 176 103 110 125 148 121 164 141 128 128 173 174 164 196 124 147 160 172 166 131 152 136 14...
output:
Tie Tie Yes 757 Yes 771 Yes 646 Yes 624 No Yes 877 No Yes 610
result:
ok 10 lines
Test #10:
score: 10
Accepted
time: 114ms
memory: 11308kb
input:
10 979 608531 888 863 899 317 456 301 490 140 103 152 188 110 116 178 183 116 143 100 132 130 142 119 165 149 120 148 176 102 142 176 172 131 128 110 165 188 182 184 164 111 151 142 144 117 182 131 171 126 132 138 123 189 119 186 113 198 162 190 101 170 119 137 104 127 184 183 137 121 186 147 108 18...
output:
Yes 788 Yes 648 Yes 536 No Yes 517 Tie Yes 787 Yes 711 Yes 657 Yes 589
result:
ok 10 lines