#include <stdio.h>
#define N 2000
#define M 2000
#define C 50
#define S (N * C)
#define INF 0x3f3f3f3f3f3f3f3fLL
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int cc[N + M], ff[N + M], vv[N + M];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ff[ii[j]] != ff[i_] ? ff[i_] - ff[ii[j]] : ii[j] - i_;
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int main() {
static int ii[N + M];
static long long dp[S + 1];
int n, m, i, s;
long long ans;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d%d", &cc[i], &ff[i], &vv[i]);
scanf("%d", &m);
for (i = n; i < n + m; i++)
scanf("%d%d%d", &cc[i], &ff[i], &vv[i]);
for (i = 0; i < n + m; i++)
ii[i] = i;
sort(ii, 0, n + m);
for (s = 1; s <= S; s++)
dp[s] = -INF;
dp[0] = 0;
for (i = 0; i < n + m; i++) {
int i_ = ii[i];
if (i_ < n) {
for (s = S; s >= cc[i_]; s--)
if (dp[s - cc[i_]] != -INF)
dp[s] = max(dp[s], dp[s - cc[i_]] - vv[i_]);
} else {
for (s = 0; s + cc[i_] <= S; s++)
if (dp[s + cc[i_]] != -INF)
dp[s] = max(dp[s], dp[s + cc[i_]] + vv[i_]);
}
}
ans = 0;
for (s = 0; s <= S; s++)
ans = max(ans, dp[s]);
printf("%lld\n", ans);
return 0;
}
Compilation message
clo.c: In function 'main':
clo.c:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
clo.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d%d%d", &cc[i], &ff[i], &vv[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
clo.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d%d", &cc[i], &ff[i], &vv[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
10 ms |
980 KB |
Output is correct |
4 |
Correct |
30 ms |
1056 KB |
Output is correct |
5 |
Correct |
138 ms |
1108 KB |
Output is correct |
6 |
Correct |
146 ms |
1128 KB |
Output is correct |
7 |
Correct |
153 ms |
1140 KB |
Output is correct |
8 |
Correct |
139 ms |
1140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1052 KB |
Output is correct |
2 |
Correct |
2 ms |
1060 KB |
Output is correct |
3 |
Correct |
12 ms |
1052 KB |
Output is correct |
4 |
Correct |
12 ms |
980 KB |
Output is correct |
5 |
Correct |
104 ms |
980 KB |
Output is correct |
6 |
Correct |
102 ms |
1108 KB |
Output is correct |
7 |
Correct |
221 ms |
1108 KB |
Output is correct |
8 |
Correct |
224 ms |
1136 KB |
Output is correct |
9 |
Correct |
227 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
980 KB |
Output is correct |
2 |
Correct |
5 ms |
1052 KB |
Output is correct |
3 |
Correct |
31 ms |
980 KB |
Output is correct |
4 |
Correct |
17 ms |
1092 KB |
Output is correct |
5 |
Correct |
35 ms |
1068 KB |
Output is correct |
6 |
Correct |
37 ms |
1068 KB |
Output is correct |
7 |
Correct |
46 ms |
1060 KB |
Output is correct |
8 |
Correct |
61 ms |
1072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
980 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
160 ms |
1108 KB |
Output is correct |
4 |
Correct |
135 ms |
1108 KB |
Output is correct |
5 |
Correct |
378 ms |
1160 KB |
Output is correct |
6 |
Correct |
427 ms |
1144 KB |
Output is correct |
7 |
Correct |
465 ms |
1152 KB |
Output is correct |
8 |
Correct |
433 ms |
1148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
980 KB |
Output is correct |
2 |
Correct |
25 ms |
980 KB |
Output is correct |
3 |
Correct |
87 ms |
980 KB |
Output is correct |
4 |
Correct |
255 ms |
1108 KB |
Output is correct |
5 |
Correct |
496 ms |
1164 KB |
Output is correct |
6 |
Correct |
518 ms |
1136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
10 ms |
980 KB |
Output is correct |
4 |
Correct |
30 ms |
1056 KB |
Output is correct |
5 |
Correct |
138 ms |
1108 KB |
Output is correct |
6 |
Correct |
146 ms |
1128 KB |
Output is correct |
7 |
Correct |
153 ms |
1140 KB |
Output is correct |
8 |
Correct |
139 ms |
1140 KB |
Output is correct |
9 |
Correct |
1 ms |
1052 KB |
Output is correct |
10 |
Correct |
2 ms |
1060 KB |
Output is correct |
11 |
Correct |
12 ms |
1052 KB |
Output is correct |
12 |
Correct |
12 ms |
980 KB |
Output is correct |
13 |
Correct |
104 ms |
980 KB |
Output is correct |
14 |
Correct |
102 ms |
1108 KB |
Output is correct |
15 |
Correct |
221 ms |
1108 KB |
Output is correct |
16 |
Correct |
224 ms |
1136 KB |
Output is correct |
17 |
Correct |
227 ms |
1108 KB |
Output is correct |
18 |
Correct |
4 ms |
980 KB |
Output is correct |
19 |
Correct |
5 ms |
1052 KB |
Output is correct |
20 |
Correct |
31 ms |
980 KB |
Output is correct |
21 |
Correct |
17 ms |
1092 KB |
Output is correct |
22 |
Correct |
35 ms |
1068 KB |
Output is correct |
23 |
Correct |
37 ms |
1068 KB |
Output is correct |
24 |
Correct |
46 ms |
1060 KB |
Output is correct |
25 |
Correct |
61 ms |
1072 KB |
Output is correct |
26 |
Correct |
3 ms |
980 KB |
Output is correct |
27 |
Correct |
3 ms |
980 KB |
Output is correct |
28 |
Correct |
160 ms |
1108 KB |
Output is correct |
29 |
Correct |
135 ms |
1108 KB |
Output is correct |
30 |
Correct |
378 ms |
1160 KB |
Output is correct |
31 |
Correct |
427 ms |
1144 KB |
Output is correct |
32 |
Correct |
465 ms |
1152 KB |
Output is correct |
33 |
Correct |
433 ms |
1148 KB |
Output is correct |
34 |
Correct |
2 ms |
980 KB |
Output is correct |
35 |
Correct |
25 ms |
980 KB |
Output is correct |
36 |
Correct |
87 ms |
980 KB |
Output is correct |
37 |
Correct |
255 ms |
1108 KB |
Output is correct |
38 |
Correct |
496 ms |
1164 KB |
Output is correct |
39 |
Correct |
518 ms |
1136 KB |
Output is correct |
40 |
Correct |
116 ms |
1108 KB |
Output is correct |
41 |
Correct |
260 ms |
1108 KB |
Output is correct |
42 |
Correct |
400 ms |
1148 KB |
Output is correct |
43 |
Correct |
570 ms |
1156 KB |
Output is correct |
44 |
Correct |
579 ms |
1164 KB |
Output is correct |
45 |
Correct |
534 ms |
1196 KB |
Output is correct |
46 |
Correct |
229 ms |
1112 KB |
Output is correct |
47 |
Correct |
322 ms |
1152 KB |
Output is correct |
48 |
Correct |
328 ms |
1148 KB |
Output is correct |