#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstring>
#include <sstream>
#pragma GCC target("popcnt")
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second
struct E{
int cores;
int hz;
int money;
};
int n,m;
E computers[2000];
E people[2000];
bool cmp(E&a,E&b){
return a.hz>b.hz;
}
ll dp1[3000][200];
ll dp2[3000][200];
int main(){
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
//freopen("speeding.in","r",stdin);
//freopen("speeding.out","w",stdout);
cin>>n;
for(int i=0;i<n;i++)
cin>>computers[i].cores>>computers[i].hz>>computers[i].money;
cin>>m;
for(int i=0;i<m;i++)
cin>>people[i].cores>>people[i].hz>>people[i].money;
sort(computers,computers+n,cmp);
sort(people,people+m,cmp);
for(int p=m-1;p>=0;p--){
for(int cores=0;cores<99;cores++){
ll res=dp2[p+1][cores];
if(people[p].cores<=cores)
res=max(res,dp2[p+1][cores-people[p].cores]+people[p].money);
dp2[p][cores]=res;
}
}
for(int c=n-1;c>=0;c--){
for(int p=m-1;p>=0;p--){
for(int cores=0;cores<200;cores++){
ll res=0;
res=max(res,dp2[p][cores]);
res=max(res,dp1[p+1][cores]);
if(people[p].cores<=cores)
res=max(res,dp1[p+1][cores-people[p].cores]+people[p].money);
if(computers[c].hz>=people[p].hz&&cores+computers[c].cores<200)
res=max(res,dp2[p][cores+computers[c].cores]-computers[c].money);
dp1[p][cores]=res;
}
}
memcpy(dp2,dp1,sizeof(dp1));
}
cout<<dp1[0][0]<<"\n";
return 0;
}
/*
4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5108 KB |
Output is correct |
4 |
Correct |
4 ms |
5276 KB |
Output is correct |
5 |
Correct |
20 ms |
8012 KB |
Output is correct |
6 |
Correct |
22 ms |
8012 KB |
Output is correct |
7 |
Correct |
25 ms |
8148 KB |
Output is correct |
8 |
Correct |
26 ms |
8192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
16 ms |
5048 KB |
Output is correct |
4 |
Correct |
16 ms |
5048 KB |
Output is correct |
5 |
Correct |
126 ms |
5076 KB |
Output is correct |
6 |
Correct |
128 ms |
5056 KB |
Output is correct |
7 |
Correct |
287 ms |
5076 KB |
Output is correct |
8 |
Correct |
279 ms |
5076 KB |
Output is correct |
9 |
Correct |
279 ms |
5076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5076 KB |
Output is correct |
3 |
Correct |
16 ms |
5076 KB |
Output is correct |
4 |
Correct |
15 ms |
5204 KB |
Output is correct |
5 |
Correct |
51 ms |
5204 KB |
Output is correct |
6 |
Correct |
51 ms |
5204 KB |
Output is correct |
7 |
Correct |
70 ms |
5412 KB |
Output is correct |
8 |
Correct |
76 ms |
5456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
206 ms |
5056 KB |
Output is correct |
4 |
Correct |
19 ms |
7764 KB |
Output is correct |
5 |
Correct |
2418 ms |
7824 KB |
Output is correct |
6 |
Correct |
2568 ms |
8184 KB |
Output is correct |
7 |
Correct |
2474 ms |
8184 KB |
Output is correct |
8 |
Correct |
2434 ms |
8156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
14 ms |
5204 KB |
Output is correct |
3 |
Correct |
163 ms |
5332 KB |
Output is correct |
4 |
Correct |
690 ms |
6920 KB |
Output is correct |
5 |
Correct |
2178 ms |
8176 KB |
Output is correct |
6 |
Correct |
2445 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5108 KB |
Output is correct |
4 |
Correct |
4 ms |
5276 KB |
Output is correct |
5 |
Correct |
20 ms |
8012 KB |
Output is correct |
6 |
Correct |
22 ms |
8012 KB |
Output is correct |
7 |
Correct |
25 ms |
8148 KB |
Output is correct |
8 |
Correct |
26 ms |
8192 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
16 ms |
5048 KB |
Output is correct |
12 |
Correct |
16 ms |
5048 KB |
Output is correct |
13 |
Correct |
126 ms |
5076 KB |
Output is correct |
14 |
Correct |
128 ms |
5056 KB |
Output is correct |
15 |
Correct |
287 ms |
5076 KB |
Output is correct |
16 |
Correct |
279 ms |
5076 KB |
Output is correct |
17 |
Correct |
279 ms |
5076 KB |
Output is correct |
18 |
Correct |
4 ms |
4948 KB |
Output is correct |
19 |
Correct |
4 ms |
5076 KB |
Output is correct |
20 |
Correct |
16 ms |
5076 KB |
Output is correct |
21 |
Correct |
15 ms |
5204 KB |
Output is correct |
22 |
Correct |
51 ms |
5204 KB |
Output is correct |
23 |
Correct |
51 ms |
5204 KB |
Output is correct |
24 |
Correct |
70 ms |
5412 KB |
Output is correct |
25 |
Correct |
76 ms |
5456 KB |
Output is correct |
26 |
Correct |
4 ms |
4948 KB |
Output is correct |
27 |
Correct |
4 ms |
4948 KB |
Output is correct |
28 |
Correct |
206 ms |
5056 KB |
Output is correct |
29 |
Correct |
19 ms |
7764 KB |
Output is correct |
30 |
Correct |
2418 ms |
7824 KB |
Output is correct |
31 |
Correct |
2568 ms |
8184 KB |
Output is correct |
32 |
Correct |
2474 ms |
8184 KB |
Output is correct |
33 |
Correct |
2434 ms |
8156 KB |
Output is correct |
34 |
Correct |
3 ms |
4948 KB |
Output is correct |
35 |
Correct |
14 ms |
5204 KB |
Output is correct |
36 |
Correct |
163 ms |
5332 KB |
Output is correct |
37 |
Correct |
690 ms |
6920 KB |
Output is correct |
38 |
Correct |
2178 ms |
8176 KB |
Output is correct |
39 |
Correct |
2445 ms |
8184 KB |
Output is correct |
40 |
Correct |
192 ms |
5856 KB |
Output is correct |
41 |
Correct |
517 ms |
6900 KB |
Output is correct |
42 |
Correct |
1336 ms |
7432 KB |
Output is correct |
43 |
Correct |
2505 ms |
8276 KB |
Output is correct |
44 |
Correct |
2506 ms |
8240 KB |
Output is correct |
45 |
Correct |
2164 ms |
8284 KB |
Output is correct |
46 |
Correct |
645 ms |
6636 KB |
Output is correct |
47 |
Correct |
1372 ms |
7444 KB |
Output is correct |
48 |
Correct |
1287 ms |
7344 KB |
Output is correct |