#include <bits/stdc++.h>
#define int int64_t //be careful about this
using namespace std;
struct item{
int type,cores,clock_rate,value;
};
signed main(){
int n;
cin >> n;
vector<item> items;
while(n--){
int c,f,v;
cin >> c >> f >> v;
items.push_back({0,c,f,v});
}
int m;
cin >> m;
while(m--){
int c,f,v;
cin >> c >> f >> v;
items.push_back({1,c,f,v});
}
sort(items.begin(), items.end(),[&](auto l,auto r){
return l.clock_rate == r.clock_rate ? l.type > r.type : l.clock_rate < r.clock_rate;
});
auto upd = [&](vector<int>& dp,int i,int profit){
while(int(dp.size()) <= i)
dp.push_back(-1e16);
if(dp[i] < profit)
dp[i] = profit;
};
vector<int> dp;
upd(dp,0,0);
for(auto [type,cores,clock_rate,value] : items){
vector<int> ndp = dp;
for(int need = 0; need < int(dp.size()); ++need){
int new_need = max(int(0),need + (type == 0 ? -1 : +1) * cores);
int new_profit = dp[need] + (type == 0 ? -1 : +1) * value;
upd(ndp,new_need,new_profit);
}
dp = ndp;
}
cout << dp[0];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
279 ms |
2720 KB |
Output is correct |
6 |
Correct |
137 ms |
1276 KB |
Output is correct |
7 |
Correct |
611 ms |
4952 KB |
Output is correct |
8 |
Correct |
645 ms |
4744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
424 KB |
Output is correct |
8 |
Correct |
5 ms |
424 KB |
Output is correct |
9 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
48 ms |
908 KB |
Output is correct |
5 |
Correct |
491 ms |
2640 KB |
Output is correct |
6 |
Correct |
983 ms |
4836 KB |
Output is correct |
7 |
Correct |
1241 ms |
4792 KB |
Output is correct |
8 |
Correct |
1211 ms |
4648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
14 ms |
564 KB |
Output is correct |
5 |
Correct |
754 ms |
4780 KB |
Output is correct |
6 |
Correct |
940 ms |
4952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
279 ms |
2720 KB |
Output is correct |
6 |
Correct |
137 ms |
1276 KB |
Output is correct |
7 |
Correct |
611 ms |
4952 KB |
Output is correct |
8 |
Correct |
645 ms |
4744 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
3 ms |
424 KB |
Output is correct |
16 |
Correct |
5 ms |
424 KB |
Output is correct |
17 |
Correct |
5 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
304 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
2 ms |
340 KB |
Output is correct |
29 |
Correct |
48 ms |
908 KB |
Output is correct |
30 |
Correct |
491 ms |
2640 KB |
Output is correct |
31 |
Correct |
983 ms |
4836 KB |
Output is correct |
32 |
Correct |
1241 ms |
4792 KB |
Output is correct |
33 |
Correct |
1211 ms |
4648 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
504 KB |
Output is correct |
36 |
Correct |
2 ms |
340 KB |
Output is correct |
37 |
Correct |
14 ms |
564 KB |
Output is correct |
38 |
Correct |
754 ms |
4780 KB |
Output is correct |
39 |
Correct |
940 ms |
4952 KB |
Output is correct |
40 |
Correct |
54 ms |
1800 KB |
Output is correct |
41 |
Correct |
274 ms |
3052 KB |
Output is correct |
42 |
Correct |
10 ms |
468 KB |
Output is correct |
43 |
Correct |
1397 ms |
5276 KB |
Output is correct |
44 |
Correct |
1289 ms |
5244 KB |
Output is correct |
45 |
Correct |
1002 ms |
5380 KB |
Output is correct |
46 |
Correct |
6 ms |
340 KB |
Output is correct |
47 |
Correct |
11 ms |
468 KB |
Output is correct |
48 |
Correct |
11 ms |
468 KB |
Output is correct |