QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #63560 | #2491. Gas and Minerals | Sa3tElSefr# | AC ✓ | 37ms | 62584kb | C++20 | 926b | 2022-11-22 18:08:19 | 2022-11-22 18:08:21 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N = 1000 + 5, mod = 998244353;
int m, g, n, a[N], b[N], c[N], dp[N][N][15];
int solve(int cur_m, int cur_g, int idx) {
if (idx == n) {
return 0;
}
auto &ret = dp[cur_m][cur_g][idx];
if (~ret) {
return ret;
}
ret = solve(cur_m, cur_g, idx + 1);
if (cur_m >= a[idx] && cur_g >= b[idx]) {
ret = max(ret, solve(cur_m - a[idx], cur_g - b[idx], idx) + c[idx]);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> g >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i] >> c[i];
}
memset(dp, -1, sizeof (dp));
cout << solve(m, g, 0) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 62480kb
input:
10 10 3 7 0 6 6 2 7 2 5 5
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 4ms
memory: 62420kb
input:
11 10 3 7 0 6 6 2 7 2 5 5
output:
16
result:
ok single line: '16'
Test #3:
score: 0
Accepted
time: 7ms
memory: 62488kb
input:
46 372 10 95 59 86 97 28 56 36 99 90 37 77 62 76 5 68 15 22 67 3 74 55 3 10 78 11 56 26 77 42 41
output:
1170
result:
ok single line: '1170'
Test #4:
score: 0
Accepted
time: 24ms
memory: 62580kb
input:
308 505 8 60 36 92 35 26 48 92 75 3 36 61 15 47 13 95 30 76 22 94 27 36 55 57 8
output:
571
result:
ok single line: '571'
Test #5:
score: 0
Accepted
time: 7ms
memory: 62416kb
input:
163 552 5 92 76 57 8 100 8 19 36 85 49 72 90 46 98 96
output:
688
result:
ok single line: '688'
Test #6:
score: 0
Accepted
time: 3ms
memory: 62480kb
input:
709 240 2 25 47 46 88 1 94
output:
796
result:
ok single line: '796'
Test #7:
score: 0
Accepted
time: 4ms
memory: 62512kb
input:
700 296 1 73 45 41
output:
246
result:
ok single line: '246'
Test #8:
score: 0
Accepted
time: 17ms
memory: 62484kb
input:
760 71 9 23 77 41 4 27 55 64 90 12 100 65 10 61 17 88 24 61 96 50 42 4 22 80 59 32 38 1
output:
352
result:
ok single line: '352'
Test #9:
score: 0
Accepted
time: 7ms
memory: 62524kb
input:
745 177 6 92 80 57 31 22 83 58 76 81 85 60 26 67 78 24 95 58 14
output:
664
result:
ok single line: '664'
Test #10:
score: 0
Accepted
time: 8ms
memory: 62420kb
input:
198 753 9 68 64 72 76 41 0 56 86 85 31 88 71 92 21 70 85 35 69 88 58 86 14 56 37 74 8 16
output:
481
result:
ok single line: '481'
Test #11:
score: 0
Accepted
time: 16ms
memory: 62396kb
input:
738 128 5 66 90 0 69 41 58 86 80 58 100 84 1 92 29 25
output:
174
result:
ok single line: '174'
Test #12:
score: 0
Accepted
time: 12ms
memory: 62520kb
input:
525 442 2 96 52 7 84 88 56
output:
280
result:
ok single line: '280'
Test #13:
score: 0
Accepted
time: 3ms
memory: 62572kb
input:
992 474 9 66 81 36 92 35 62 65 68 34 38 36 96 23 41 33 64 95 45 14 65 64 71 84 4 29 83 12
output:
1248
result:
ok single line: '1248'
Test #14:
score: 0
Accepted
time: 12ms
memory: 62484kb
input:
216 279 7 43 29 62 63 90 43 96 35 49 36 55 91 9 89 39 34 82 61 82 11 13
output:
455
result:
ok single line: '455'
Test #15:
score: 0
Accepted
time: 19ms
memory: 62400kb
input:
440 941 1 88 63 33
output:
165
result:
ok single line: '165'
Test #16:
score: 0
Accepted
time: 3ms
memory: 62396kb
input:
140 530 5 78 34 77 96 68 66 74 20 57 53 85 59 2 45 84
output:
1001
result:
ok single line: '1001'
Test #17:
score: 0
Accepted
time: 11ms
memory: 62416kb
input:
171 269 6 46 85 58 27 29 56 39 38 47 13 85 38 91 33 38 52 38 36
output:
336
result:
ok single line: '336'
Test #18:
score: 0
Accepted
time: 17ms
memory: 62496kb
input:
122 692 1 57 23 93
output:
186
result:
ok single line: '186'
Test #19:
score: 0
Accepted
time: 15ms
memory: 62480kb
input:
77 51 8 75 77 69 26 33 94 33 9 39 99 77 30 38 76 33 45 9 84 74 71 36 76 90 75
output:
178
result:
ok single line: '178'
Test #20:
score: 0
Accepted
time: 12ms
memory: 62572kb
input:
920 703 2 84 12 55 2 54 90
output:
1485
result:
ok single line: '1485'
Test #21:
score: 0
Accepted
time: 7ms
memory: 62516kb
input:
408 880 2 79 6 9 98 17 72
output:
288
result:
ok single line: '288'
Test #22:
score: 0
Accepted
time: 3ms
memory: 62520kb
input:
602 629 6 78 88 9 54 4 19 27 70 78 98 68 86 14 40 76 12 58 56
output:
1273
result:
ok single line: '1273'
Test #23:
score: 0
Accepted
time: 14ms
memory: 62420kb
input:
841 485 4 89 3 25 20 13 35 38 17 37 90 30 77
output:
1320
result:
ok single line: '1320'
Test #24:
score: 0
Accepted
time: 15ms
memory: 62568kb
input:
550 923 9 63 87 19 67 96 38 99 41 58 13 94 63 38 81 31 1 21 39 90 93 38 30 31 4 26 51 24
output:
1696
result:
ok single line: '1696'
Test #25:
score: 0
Accepted
time: 8ms
memory: 62412kb
input:
937 75 7 59 66 42 75 5 49 55 99 47 59 26 24 13 77 45 22 3 11 60 39 46
output:
599
result:
ok single line: '599'
Test #26:
score: 0
Accepted
time: 37ms
memory: 62512kb
input:
631 804 7 7 8 40 88 7 73 40 60 88 1 100 38 31 16 0 97 6 41 53 48 80
output:
3600
result:
ok single line: '3600'
Test #27:
score: 0
Accepted
time: 8ms
memory: 62520kb
input:
356 565 3 73 11 88 58 0 20 4 75 36
output:
568
result:
ok single line: '568'
Test #28:
score: 0
Accepted
time: 16ms
memory: 62420kb
input:
667 60 6 56 87 43 41 17 93 39 90 85 79 78 78 49 34 74 66 73 74
output:
279
result:
ok single line: '279'
Test #29:
score: 0
Accepted
time: 7ms
memory: 62420kb
input:
335 558 8 77 52 51 65 63 81 43 17 0 1 44 82 81 66 10 21 27 100 61 85 5 17 59 77
output:
1746
result:
ok single line: '1746'
Test #30:
score: 0
Accepted
time: 12ms
memory: 62412kb
input:
76 885 1 90 63 0
output:
0
result:
ok single line: '0'
Test #31:
score: 0
Accepted
time: 13ms
memory: 62420kb
input:
771 557 4 94 21 9 11 79 89 25 98 97 37 66 81
output:
664
result:
ok single line: '664'
Test #32:
score: 0
Accepted
time: 16ms
memory: 62508kb
input:
566 956 1 4 34 97
output:
2716
result:
ok single line: '2716'
Test #33:
score: 0
Accepted
time: 11ms
memory: 62416kb
input:
196 999 7 36 60 42 47 98 47 21 53 82 94 11 40 78 79 72 47 23 44 48 28 99
output:
738
result:
ok single line: '738'
Test #34:
score: 0
Accepted
time: 9ms
memory: 62400kb
input:
636 376 4 5 70 67 14 60 81 53 42 0 64 27 71
output:
801
result:
ok single line: '801'
Test #35:
score: 0
Accepted
time: 7ms
memory: 62492kb
input:
327 133 3 12 25 44 65 11 43 63 75 58
output:
305
result:
ok single line: '305'
Test #36:
score: 0
Accepted
time: 18ms
memory: 62452kb
input:
289 356 6 22 1 19 50 55 12 29 46 1 7 8 99 18 95 1 28 60 10
output:
4059
result:
ok single line: '4059'
Test #37:
score: 0
Accepted
time: 8ms
memory: 62572kb
input:
16 986 8 26 40 62 3 5 96 28 65 72 90 20 70 76 82 100 78 64 100 31 14 88 61 90 52
output:
480
result:
ok single line: '480'
Test #38:
score: 0
Accepted
time: 24ms
memory: 62520kb
input:
759 833 8 71 94 58 98 88 89 81 59 63 90 28 60 31 23 34 11 14 93 94 33 50 66 87 74
output:
5487
result:
ok single line: '5487'
Test #39:
score: 0
Accepted
time: 4ms
memory: 62420kb
input:
552 893 1 5 46 54
output:
1026
result:
ok single line: '1026'
Test #40:
score: 0
Accepted
time: 7ms
memory: 62420kb
input:
676 66 10 6 48 59 53 20 73 48 33 36 37 45 36 10 11 20 12 25 46 67 86 13 71 58 84 7 23 24 94 6 32
output:
274
result:
ok single line: '274'
Test #41:
score: 0
Accepted
time: 12ms
memory: 62420kb
input:
332 136 1 8 61 78
output:
156
result:
ok single line: '156'
Test #42:
score: 0
Accepted
time: 12ms
memory: 62568kb
input:
977 539 1 69 68 54
output:
378
result:
ok single line: '378'
Test #43:
score: 0
Accepted
time: 9ms
memory: 62448kb
input:
42 369 5 86 83 14 22 60 26 6 100 76 12 11 48 53 2 71
output:
324
result:
ok single line: '324'
Test #44:
score: 0
Accepted
time: 7ms
memory: 62508kb
input:
876 590 4 59 15 48 51 72 22 65 19 53 72 77 61
output:
727
result:
ok single line: '727'
Test #45:
score: 0
Accepted
time: 8ms
memory: 62416kb
input:
868 453 3 9 59 66 48 27 45 29 50 55
output:
720
result:
ok single line: '720'
Test #46:
score: 0
Accepted
time: 0ms
memory: 62516kb
input:
264 859 6 39 70 50 94 26 39 63 29 5 62 1 24 83 26 83 74 34 48
output:
300
result:
ok single line: '300'
Test #47:
score: 0
Accepted
time: 9ms
memory: 62508kb
input:
573 25 5 84 8 18 90 42 66 33 71 97 95 2 81 51 48 94
output:
486
result:
ok single line: '486'
Test #48:
score: 0
Accepted
time: 12ms
memory: 62400kb
input:
29 538 1 1 77 37
output:
222
result:
ok single line: '222'
Test #49:
score: 0
Accepted
time: 8ms
memory: 62480kb
input:
1 757 5 83 93 41 90 51 46 20 3 11 2 64 50 69 55 75
output:
0
result:
ok single line: '0'
Test #50:
score: 0
Accepted
time: 18ms
memory: 62504kb
input:
590 319 1 90 18 1
output:
6
result:
ok single line: '6'
Test #51:
score: 0
Accepted
time: 7ms
memory: 62572kb
input:
735 189 4 20 34 45 83 21 34 15 2 75 68 39 44
output:
3675
result:
ok single line: '3675'
Test #52:
score: 0
Accepted
time: 7ms
memory: 62516kb
input:
541 613 4 82 24 60 7 72 21 17 3 44 87 64 13
output:
1406
result:
ok single line: '1406'
Test #53:
score: 0
Accepted
time: 9ms
memory: 62476kb
input:
890 126 2 50 85 66 85 47 33
output:
66
result:
ok single line: '66'
Test #54:
score: 0
Accepted
time: 14ms
memory: 62504kb
input:
312 355 2 42 99 73 85 34 100
output:
373
result:
ok single line: '373'
Test #55:
score: 0
Accepted
time: 7ms
memory: 62564kb
input:
383 17 1 83 1 85
output:
340
result:
ok single line: '340'
Test #56:
score: 0
Accepted
time: 12ms
memory: 62416kb
input:
673 689 6 60 14 6 96 32 84 26 38 45 99 88 87 9 57 22 34 53 100
output:
1352
result:
ok single line: '1352'
Test #57:
score: 0
Accepted
time: 23ms
memory: 62452kb
input:
418 727 4 11 43 26 14 29 9 49 17 77 59 9 17
output:
758
result:
ok single line: '758'
Test #58:
score: 0
Accepted
time: 4ms
memory: 62484kb
input:
862 823 1 6 80 81
output:
810
result:
ok single line: '810'
Test #59:
score: 0
Accepted
time: 20ms
memory: 62480kb
input:
649 671 8 96 94 41 45 67 82 15 49 64 38 69 99 84 31 80 37 43 44 16 71 37 32 80 88
output:
1081
result:
ok single line: '1081'
Test #60:
score: 0
Accepted
time: 8ms
memory: 62488kb
input:
929 152 1 45 8 24
output:
456
result:
ok single line: '456'
Test #61:
score: 0
Accepted
time: 11ms
memory: 62420kb
input:
23 346 7 46 56 56 47 10 36 47 25 40 35 73 63 59 53 43 39 78 71 65 87 92
output:
0
result:
ok single line: '0'
Test #62:
score: 0
Accepted
time: 9ms
memory: 62524kb
input:
3 475 4 12 67 5 97 72 1 45 46 75 66 4 68
output:
0
result:
ok single line: '0'
Test #63:
score: 0
Accepted
time: 22ms
memory: 62484kb
input:
373 313 7 48 3 7 96 63 75 49 98 1 41 28 55 61 86 12 38 100 3 28 14 7
output:
495
result:
ok single line: '495'
Test #64:
score: 0
Accepted
time: 9ms
memory: 62480kb
input:
391 974 6 48 60 68 95 96 58 48 92 25 4 25 26 58 70 25 64 32 75
output:
1158
result:
ok single line: '1158'
Test #65:
score: 0
Accepted
time: 10ms
memory: 62420kb
input:
908 323 3 35 30 59 78 22 27 22 22 61
output:
854
result:
ok single line: '854'
Test #66:
score: 0
Accepted
time: 11ms
memory: 62520kb
input:
449 898 4 93 58 99 37 17 59 26 99 90 71 71 97
output:
1074
result:
ok single line: '1074'
Test #67:
score: 0
Accepted
time: 18ms
memory: 62584kb
input:
721 104 10 59 26 54 85 19 46 51 35 35 32 36 93 86 42 76 30 92 59 6 52 49 5 82 35 17 38 51 66 38 10
output:
240
result:
ok single line: '240'
Test #68:
score: 0
Accepted
time: 13ms
memory: 62508kb
input:
805 362 6 99 82 34 23 25 89 76 33 83 10 98 78 81 44 9 55 73 63
output:
1246
result:
ok single line: '1246'
Test #69:
score: 0
Accepted
time: 12ms
memory: 62484kb
input:
841 649 2 52 43 61 31 29 33
output:
915
result:
ok single line: '915'
Test #70:
score: 0
Accepted
time: 4ms
memory: 62516kb
input:
785 273 5 62 16 97 49 37 95 10 47 6 22 80 99 98 36 97
output:
1263
result:
ok single line: '1263'
Test #71:
score: 0
Accepted
time: 7ms
memory: 62472kb
input:
355 477 3 62 48 18 53 53 44 81 51 54
output:
274
result:
ok single line: '274'
Test #72:
score: 0
Accepted
time: 8ms
memory: 62476kb
input:
193 692 9 37 14 25 20 95 91 29 18 64 87 88 24 87 13 98 92 89 27 60 41 49 27 16 61 72 72 2
output:
701
result:
ok single line: '701'
Test #73:
score: 0
Accepted
time: 12ms
memory: 62452kb
input:
237 440 10 6 20 66 100 10 15 79 42 15 7 67 62 17 59 12 77 49 59 94 45 49 15 4 40 37 79 12 77 17 2
output:
1600
result:
ok single line: '1600'
Test #74:
score: 0
Accepted
time: 12ms
memory: 62584kb
input:
297 741 4 35 89 93 81 6 21 34 25 92 32 13 75
output:
744
result:
ok single line: '744'
Test #75:
score: 0
Accepted
time: 8ms
memory: 62476kb
input:
388 261 1 49 90 27
output:
54
result:
ok single line: '54'