#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define NINF -1000000000000000LL;
/* Date: 9/5/21
* Link: https://oj.uz/problem/view/CEOI18_clo
* Verdict: WA (72/100), AC
*/
struct Option {
int c, f, v;
Option(int _c, int _f, int _v) {
c = _c; f = _f; v = _v;
}
inline bool operator<(const Option& o) {
if (f != o.f) {
return f > o.f;
}
return v < o.v;
}
};
vector<Option> options;
LL dp[2][100005];
int N, M;
int main() {
ios::sync_with_stdio(0);
for (int i = 0; i < 100005; i++) {
dp[0][i] = NINF;
dp[1][i] = NINF;
}
cin >> N;
for (int i = 0; i < N; i++) {
int c, f, v;
cin >> c >> f >> v;
options.push_back(Option(c, f, -v));
}
cin >> M;
for (int i = 0; i < M; i++) {
int c, f, v;
cin >> c >> f >> v;
options.push_back(Option(-c, f, v));
}
sort(options.begin(), options.end());
int crow = 0;
int rrow = 1;
const int len = N+M;
dp[0][0] = 0;
for (int i = 0; i < len; i++) {
const int cc = options[i].c;
const int cv = options[i].v;
const int lim = min(100000, 100000+cc);
const int start = max(0, cc);
for (int j = start; j <= lim; j++) {
dp[rrow][j] = max(dp[crow][j], dp[crow][j-cc]+cv);
}
for (int j = 0; j < start; j++) {
dp[rrow][j] = dp[crow][j];
}
for (int j = lim+1; j <= 100000; j++) {
dp[rrow][j] = dp[crow][j];
}
crow = rrow;
rrow = 1 ^ rrow;
}
LL ans = 0;
for (int i = 0; i <= 100000; i++) {
ans = max(ans, dp[crow][i]);
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1868 KB |
Output is correct |
2 |
Correct |
2 ms |
1868 KB |
Output is correct |
3 |
Correct |
13 ms |
1868 KB |
Output is correct |
4 |
Correct |
24 ms |
1868 KB |
Output is correct |
5 |
Correct |
217 ms |
1988 KB |
Output is correct |
6 |
Correct |
220 ms |
1912 KB |
Output is correct |
7 |
Correct |
280 ms |
1908 KB |
Output is correct |
8 |
Correct |
231 ms |
1868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1868 KB |
Output is correct |
2 |
Correct |
2 ms |
1868 KB |
Output is correct |
3 |
Correct |
13 ms |
1876 KB |
Output is correct |
4 |
Correct |
13 ms |
1884 KB |
Output is correct |
5 |
Correct |
107 ms |
1884 KB |
Output is correct |
6 |
Correct |
105 ms |
1868 KB |
Output is correct |
7 |
Correct |
223 ms |
1908 KB |
Output is correct |
8 |
Correct |
223 ms |
1904 KB |
Output is correct |
9 |
Correct |
212 ms |
1868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1868 KB |
Output is correct |
2 |
Correct |
5 ms |
1868 KB |
Output is correct |
3 |
Correct |
21 ms |
1868 KB |
Output is correct |
4 |
Correct |
24 ms |
1892 KB |
Output is correct |
5 |
Correct |
41 ms |
1884 KB |
Output is correct |
6 |
Correct |
42 ms |
1868 KB |
Output is correct |
7 |
Correct |
56 ms |
1868 KB |
Output is correct |
8 |
Correct |
57 ms |
1868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1868 KB |
Output is correct |
2 |
Correct |
3 ms |
1880 KB |
Output is correct |
3 |
Correct |
164 ms |
1904 KB |
Output is correct |
4 |
Correct |
206 ms |
1908 KB |
Output is correct |
5 |
Correct |
414 ms |
1956 KB |
Output is correct |
6 |
Correct |
461 ms |
1988 KB |
Output is correct |
7 |
Correct |
438 ms |
1956 KB |
Output is correct |
8 |
Correct |
446 ms |
1956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1868 KB |
Output is correct |
2 |
Correct |
19 ms |
1868 KB |
Output is correct |
3 |
Correct |
92 ms |
1884 KB |
Output is correct |
4 |
Correct |
238 ms |
1908 KB |
Output is correct |
5 |
Correct |
435 ms |
1964 KB |
Output is correct |
6 |
Correct |
451 ms |
1988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1868 KB |
Output is correct |
2 |
Correct |
2 ms |
1868 KB |
Output is correct |
3 |
Correct |
13 ms |
1868 KB |
Output is correct |
4 |
Correct |
24 ms |
1868 KB |
Output is correct |
5 |
Correct |
217 ms |
1988 KB |
Output is correct |
6 |
Correct |
220 ms |
1912 KB |
Output is correct |
7 |
Correct |
280 ms |
1908 KB |
Output is correct |
8 |
Correct |
231 ms |
1868 KB |
Output is correct |
9 |
Correct |
3 ms |
1868 KB |
Output is correct |
10 |
Correct |
2 ms |
1868 KB |
Output is correct |
11 |
Correct |
13 ms |
1876 KB |
Output is correct |
12 |
Correct |
13 ms |
1884 KB |
Output is correct |
13 |
Correct |
107 ms |
1884 KB |
Output is correct |
14 |
Correct |
105 ms |
1868 KB |
Output is correct |
15 |
Correct |
223 ms |
1908 KB |
Output is correct |
16 |
Correct |
223 ms |
1904 KB |
Output is correct |
17 |
Correct |
212 ms |
1868 KB |
Output is correct |
18 |
Correct |
4 ms |
1868 KB |
Output is correct |
19 |
Correct |
5 ms |
1868 KB |
Output is correct |
20 |
Correct |
21 ms |
1868 KB |
Output is correct |
21 |
Correct |
24 ms |
1892 KB |
Output is correct |
22 |
Correct |
41 ms |
1884 KB |
Output is correct |
23 |
Correct |
42 ms |
1868 KB |
Output is correct |
24 |
Correct |
56 ms |
1868 KB |
Output is correct |
25 |
Correct |
57 ms |
1868 KB |
Output is correct |
26 |
Correct |
3 ms |
1868 KB |
Output is correct |
27 |
Correct |
3 ms |
1880 KB |
Output is correct |
28 |
Correct |
164 ms |
1904 KB |
Output is correct |
29 |
Correct |
206 ms |
1908 KB |
Output is correct |
30 |
Correct |
414 ms |
1956 KB |
Output is correct |
31 |
Correct |
461 ms |
1988 KB |
Output is correct |
32 |
Correct |
438 ms |
1956 KB |
Output is correct |
33 |
Correct |
446 ms |
1956 KB |
Output is correct |
34 |
Correct |
2 ms |
1868 KB |
Output is correct |
35 |
Correct |
19 ms |
1868 KB |
Output is correct |
36 |
Correct |
92 ms |
1884 KB |
Output is correct |
37 |
Correct |
238 ms |
1908 KB |
Output is correct |
38 |
Correct |
435 ms |
1964 KB |
Output is correct |
39 |
Correct |
451 ms |
1988 KB |
Output is correct |
40 |
Correct |
113 ms |
1884 KB |
Output is correct |
41 |
Correct |
217 ms |
1912 KB |
Output is correct |
42 |
Correct |
335 ms |
1944 KB |
Output is correct |
43 |
Correct |
435 ms |
1956 KB |
Output is correct |
44 |
Correct |
452 ms |
1964 KB |
Output is correct |
45 |
Correct |
488 ms |
1868 KB |
Output is correct |
46 |
Correct |
225 ms |
1868 KB |
Output is correct |
47 |
Correct |
331 ms |
1944 KB |
Output is correct |
48 |
Correct |
332 ms |
1960 KB |
Output is correct |