#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Transaction {
int c, f, v;
bool operator <(const Transaction& other) { return f > other.f; }
};
ll dp[2][100001];
int main() {
vector<Transaction> trans;
int n; cin >> n;
for(int i = 0; i < n; i++) {
trans.push_back(Transaction());
int c, f, v;
cin >> c >> f >> v;
trans[i].c = c;
trans[i].f = f;
trans[i].v = -v;
}
int m; cin >> m;
for(int i = 0; i < m; i++) {
trans.push_back(Transaction());
int C, F, V;
cin >> C >> F >> V;
trans[n+i].c = -C;
trans[n+i].f = F;
trans[n+i].v = V;
}
sort(trans.begin(), trans.end());
for(int j = 0; j <= 100000; j++) dp[0][j] = INT64_MIN;
dp[0][0] = 0;
for(int t = 0; t < n+m; t++) {
Transaction tn = trans[t];
copy(begin(dp[0]), end(dp[0]), begin(dp[1]));
for(int c = 100000; c >= max(tn.c, 0); c--) {
if(c-tn.c <= 100000 && dp[0][c-tn.c] != INT64_MIN)
dp[1][c] = max(dp[1][c], dp[0][c-tn.c] + tn.v);
// if(dp[1][c] != INT_MIN) {
// cout << "t: " << t << " c : " << c << endl;
// cout << "c-tnc: " << dp[1][c-tn.c] << " v: " << tn.v << endl;
// cout << "dp: " << dp[1][c] << endl;
// }
}
swap(dp[0], dp[1]);
}
ll res = 0;
for(ll l : dp[0]) res = max(res, l);
cout << res << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
22 ms |
1860 KB |
Output is correct |
4 |
Correct |
41 ms |
1740 KB |
Output is correct |
5 |
Correct |
372 ms |
1868 KB |
Output is correct |
6 |
Correct |
394 ms |
1884 KB |
Output is correct |
7 |
Correct |
392 ms |
1896 KB |
Output is correct |
8 |
Correct |
403 ms |
1992 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1740 KB |
Output is correct |
2 |
Correct |
5 ms |
1856 KB |
Output is correct |
3 |
Correct |
22 ms |
1740 KB |
Output is correct |
4 |
Correct |
23 ms |
1856 KB |
Output is correct |
5 |
Correct |
184 ms |
1868 KB |
Output is correct |
6 |
Correct |
180 ms |
1988 KB |
Output is correct |
7 |
Correct |
399 ms |
1884 KB |
Output is correct |
8 |
Correct |
444 ms |
1880 KB |
Output is correct |
9 |
Correct |
389 ms |
1868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
1740 KB |
Output is correct |
2 |
Correct |
7 ms |
1856 KB |
Output is correct |
3 |
Correct |
36 ms |
1740 KB |
Output is correct |
4 |
Correct |
37 ms |
1852 KB |
Output is correct |
5 |
Correct |
72 ms |
1740 KB |
Output is correct |
6 |
Correct |
72 ms |
1868 KB |
Output is correct |
7 |
Correct |
105 ms |
1868 KB |
Output is correct |
8 |
Correct |
107 ms |
1868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
1868 KB |
Output is correct |
2 |
Correct |
4 ms |
1740 KB |
Output is correct |
3 |
Correct |
317 ms |
1988 KB |
Output is correct |
4 |
Incorrect |
350 ms |
1880 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1740 KB |
Output is correct |
2 |
Correct |
35 ms |
1864 KB |
Output is correct |
3 |
Correct |
163 ms |
1868 KB |
Output is correct |
4 |
Correct |
386 ms |
1888 KB |
Output is correct |
5 |
Correct |
781 ms |
1868 KB |
Output is correct |
6 |
Correct |
811 ms |
1988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
22 ms |
1860 KB |
Output is correct |
4 |
Correct |
41 ms |
1740 KB |
Output is correct |
5 |
Correct |
372 ms |
1868 KB |
Output is correct |
6 |
Correct |
394 ms |
1884 KB |
Output is correct |
7 |
Correct |
392 ms |
1896 KB |
Output is correct |
8 |
Correct |
403 ms |
1992 KB |
Output is correct |
9 |
Correct |
2 ms |
1740 KB |
Output is correct |
10 |
Correct |
5 ms |
1856 KB |
Output is correct |
11 |
Correct |
22 ms |
1740 KB |
Output is correct |
12 |
Correct |
23 ms |
1856 KB |
Output is correct |
13 |
Correct |
184 ms |
1868 KB |
Output is correct |
14 |
Correct |
180 ms |
1988 KB |
Output is correct |
15 |
Correct |
399 ms |
1884 KB |
Output is correct |
16 |
Correct |
444 ms |
1880 KB |
Output is correct |
17 |
Correct |
389 ms |
1868 KB |
Output is correct |
18 |
Correct |
7 ms |
1740 KB |
Output is correct |
19 |
Correct |
7 ms |
1856 KB |
Output is correct |
20 |
Correct |
36 ms |
1740 KB |
Output is correct |
21 |
Correct |
37 ms |
1852 KB |
Output is correct |
22 |
Correct |
72 ms |
1740 KB |
Output is correct |
23 |
Correct |
72 ms |
1868 KB |
Output is correct |
24 |
Correct |
105 ms |
1868 KB |
Output is correct |
25 |
Correct |
107 ms |
1868 KB |
Output is correct |
26 |
Correct |
7 ms |
1868 KB |
Output is correct |
27 |
Correct |
4 ms |
1740 KB |
Output is correct |
28 |
Correct |
317 ms |
1988 KB |
Output is correct |
29 |
Incorrect |
350 ms |
1880 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |