#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int n, m;
struct computer {
int cores = 0;
ll speed = 0, money = 0;
};
vector <computer> sellers, buyers;
bool comp(computer a, computer b) {
return a.speed < b.speed;
}
vector <vector <vector <ll>>> dp;
ll solve(int i, int rem, int j) {
if (j == 0)
return 0;
if (dp[i][rem][j] != -1e16)
return dp[i][rem][j];
ll ans = solve(i, rem, j-1);
// buyers buy from cores bought by sellers
if (rem >= buyers[j].cores) {
if (sellers[i+1].speed >= buyers[j].speed)
ans = max(ans, solve(i, rem - buyers[j].cores, j-1) + buyers[j].money);
}
// sellers buy cores
if (i >= 1 && rem <= 50) {
ans = max(ans, solve(i-1, rem, j));
ans = max(ans, solve(i-1, rem + sellers[i].cores, j) - sellers[i].money);
}
dp[i][rem][j] = ans;
return ans;
}
int main() {
// freopen("in.txt", "r", stdin);
cin >> n;
sellers.resize(n+1);
for (int i = 1; i <= n; i++)
cin >> sellers[i].cores >> sellers[i].speed >> sellers[i].money;
cin >> m;
buyers.resize(m+1);
for (int i = 1; i <= m; i++)
cin >> buyers[i].cores >> buyers[i].speed >> buyers[i].money;
sort(sellers.begin(), sellers.end(), comp);
sort(buyers.begin(), buyers.end(), comp);
dp = vector <vector <vector <ll>>> (n+1, vector <vector <ll>> (101, vector <ll> (m+1, -1e16)));
cout << max((ll)0, solve(n, 0, m)) << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
2 ms |
1884 KB |
Output is correct |
5 |
Correct |
53 ms |
26260 KB |
Output is correct |
6 |
Correct |
17 ms |
26204 KB |
Output is correct |
7 |
Correct |
41 ms |
27616 KB |
Output is correct |
8 |
Correct |
49 ms |
27484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
1112 KB |
Output is correct |
4 |
Correct |
2 ms |
1116 KB |
Output is correct |
5 |
Correct |
44 ms |
14116 KB |
Output is correct |
6 |
Correct |
34 ms |
14092 KB |
Output is correct |
7 |
Correct |
163 ms |
33880 KB |
Output is correct |
8 |
Correct |
101 ms |
33884 KB |
Output is correct |
9 |
Correct |
166 ms |
32872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
8 ms |
7000 KB |
Output is correct |
4 |
Correct |
9 ms |
7180 KB |
Output is correct |
5 |
Correct |
51 ms |
26204 KB |
Output is correct |
6 |
Correct |
50 ms |
26200 KB |
Output is correct |
7 |
Correct |
108 ms |
51292 KB |
Output is correct |
8 |
Correct |
110 ms |
51096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
21 ms |
15964 KB |
Output is correct |
4 |
Correct |
52 ms |
22108 KB |
Output is correct |
5 |
Runtime error |
102 ms |
262144 KB |
Execution killed with signal 9 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
4 ms |
5208 KB |
Output is correct |
3 |
Correct |
553 ms |
114024 KB |
Output is correct |
4 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
2 ms |
1884 KB |
Output is correct |
5 |
Correct |
53 ms |
26260 KB |
Output is correct |
6 |
Correct |
17 ms |
26204 KB |
Output is correct |
7 |
Correct |
41 ms |
27616 KB |
Output is correct |
8 |
Correct |
49 ms |
27484 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
1112 KB |
Output is correct |
12 |
Correct |
2 ms |
1116 KB |
Output is correct |
13 |
Correct |
44 ms |
14116 KB |
Output is correct |
14 |
Correct |
34 ms |
14092 KB |
Output is correct |
15 |
Correct |
163 ms |
33880 KB |
Output is correct |
16 |
Correct |
101 ms |
33884 KB |
Output is correct |
17 |
Correct |
166 ms |
32872 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
0 ms |
600 KB |
Output is correct |
20 |
Correct |
8 ms |
7000 KB |
Output is correct |
21 |
Correct |
9 ms |
7180 KB |
Output is correct |
22 |
Correct |
51 ms |
26204 KB |
Output is correct |
23 |
Correct |
50 ms |
26200 KB |
Output is correct |
24 |
Correct |
108 ms |
51292 KB |
Output is correct |
25 |
Correct |
110 ms |
51096 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
21 ms |
15964 KB |
Output is correct |
29 |
Correct |
52 ms |
22108 KB |
Output is correct |
30 |
Runtime error |
102 ms |
262144 KB |
Execution killed with signal 9 |
31 |
Halted |
0 ms |
0 KB |
- |