#include <bits/stdc++.h>
/*
Start 14:37 PM
All tasks are performed simultaneously
~ 100000 cores
Price up to 10^9; binsearch?
O(nm log n log m)
ST1: ?
ST2: ?
ST3: Potential O(n^3)
One-to-one match between machines and customers
Start highest computer first
Buying/selling events
Number of computers,
ST4: There is only a number of cores. DP for min cost over number of cores to sell and buy in O(n sum(c_i) + m sum(C_j))
ST5:
*/
struct obj{
int cores;
int power;
int cost;
obj(int a,int b,int c):cores(a),power(b),cost(c){}
};
std::vector<obj> comps;
std::vector<obj> reqs;
int main(){
int n,m,nc=0;
std::cin>>n;
std::vector<int> sorted;
for(int i=0;i<n;i++){
int c,f,v;
std::cin>>c>>f>>v;
comps.push_back(obj(c,f,v));
sorted.push_back(i);
nc+=c;
}
std::cin>>m;
for(int i=0;i<m;i++){
int c,f,v;
std::cin>>c>>f>>v;
reqs.push_back(obj(c,f,v));
sorted.push_back(~i);
}
std::sort(sorted.begin(),sorted.end(),[](int a,int b){
int csa=a>=0?comps[a].power:reqs[~a].power;
int csb=b>=0?comps[b].power:reqs[~b].power;
return csa==csb?a>b:csa>csb;
});
std::vector<long long> dp(nc+1,-(1ll<<62));
dp[0]=0;
for(int i=0;i<n+m;i++){
std::vector<long long> dp_new(dp);
int cur=sorted[i];
if(cur>=0){
//std::cout<<"cost "<<comps[cur].cost<<" computer\n";
for(int j=nc;j>=comps[cur].cores;j--){
dp_new[j]=std::max(dp[j],dp[j-comps[cur].cores]-comps[cur].cost);
}
}else{
cur=~cur;
//std::cout<<"cost "<<reqs[cur].cost<<" customer\n";
for(int j=0;j<=nc-reqs[cur].cores;j++){
dp_new[j]=std::max(dp[j],dp[j+reqs[cur].cores]+reqs[cur].cost);
}
}
dp=dp_new;
/*
for(long long i:dp){
std::cout<<i<<' ';
}
std::cout<<'\n';
*/
}
long long mx=0;
for(int i=0;i<nc;i++){
mx=std::max(mx,dp[i]);
}
std::cout<<mx<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
3 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
340 KB |
Output is correct |
8 |
Correct |
4 ms |
372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
32 ms |
664 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
140 ms |
1140 KB |
Output is correct |
8 |
Correct |
27 ms |
492 KB |
Output is correct |
9 |
Correct |
221 ms |
1704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
10 ms |
428 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
274 ms |
1236 KB |
Output is correct |
6 |
Correct |
511 ms |
1808 KB |
Output is correct |
7 |
Correct |
492 ms |
1808 KB |
Output is correct |
8 |
Correct |
516 ms |
1812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
28 ms |
724 KB |
Output is correct |
4 |
Correct |
9 ms |
340 KB |
Output is correct |
5 |
Correct |
470 ms |
1820 KB |
Output is correct |
6 |
Correct |
498 ms |
1812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
3 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
340 KB |
Output is correct |
8 |
Correct |
4 ms |
372 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
300 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
32 ms |
664 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
140 ms |
1140 KB |
Output is correct |
16 |
Correct |
27 ms |
492 KB |
Output is correct |
17 |
Correct |
221 ms |
1704 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
10 ms |
428 KB |
Output is correct |
29 |
Correct |
2 ms |
340 KB |
Output is correct |
30 |
Correct |
274 ms |
1236 KB |
Output is correct |
31 |
Correct |
511 ms |
1808 KB |
Output is correct |
32 |
Correct |
492 ms |
1808 KB |
Output is correct |
33 |
Correct |
516 ms |
1812 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
28 ms |
724 KB |
Output is correct |
37 |
Correct |
9 ms |
340 KB |
Output is correct |
38 |
Correct |
470 ms |
1820 KB |
Output is correct |
39 |
Correct |
498 ms |
1812 KB |
Output is correct |
40 |
Correct |
31 ms |
672 KB |
Output is correct |
41 |
Correct |
93 ms |
852 KB |
Output is correct |
42 |
Correct |
8 ms |
436 KB |
Output is correct |
43 |
Correct |
534 ms |
2016 KB |
Output is correct |
44 |
Correct |
545 ms |
2004 KB |
Output is correct |
45 |
Correct |
526 ms |
2004 KB |
Output is correct |
46 |
Correct |
4 ms |
312 KB |
Output is correct |
47 |
Correct |
8 ms |
352 KB |
Output is correct |
48 |
Correct |
8 ms |
340 KB |
Output is correct |