#include <bits/stdc++.h>
using namespace std ;
const int MAX = 2010 ;
struct computer
{
int c , f , v , id ;
};
int mark[MAX] ;
int n , m ;
computer arr[MAX+MAX] ;
long long dp[2][(MAX+MAX)*52] ;
bool cmp(computer &a , computer &b)
{
if(a.f != b.f)
return a.f > b.f ;
else
return a.id < b.id ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 1 ; i <= n ; ++i)
{
cin>>arr[i].c>>arr[i].f>>arr[i].v ;
arr[i].id = i ;
}
cin>>m ;
for(int i = n+1 ; i <= n+m ; ++i)
{
cin>>arr[i].c>>arr[i].f>>arr[i].v ;
arr[i].id = i ;
}
sort(arr+1 , arr+n+m+1 , cmp) ;
long long ans = 0ll ;
for(int j = 1 ; j <= (n+m)*50 ; ++j)
dp[0][j] = -1e14 ;
for(int i = 1 ; i <= n+m ; ++i)
{
for(int j = 0 ; j <= (n+m)*50 ; ++j)
{
dp[i&1][j] = dp[(i-1)&1][j] ;
if(arr[i].id <= n)
{
if(j - arr[i].c >= 0)
dp[i&1][j] = max(dp[i&1][j] , dp[(i-1)&1][j-arr[i].c]-arr[i].v) ;
}
else if(arr[i].id > n)
{
if(j+arr[i].c <= (n+m)*50)
dp[i&1][j] = max(dp[i&1][j] , dp[(i-1)&1][arr[i].c+j] + arr[i].v) ;
}
ans = max(ans , dp[i&1][j]) ;
}
}
return cout<<ans<<"\n" , 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
317 ms |
1892 KB |
Output is correct |
6 |
Correct |
317 ms |
1876 KB |
Output is correct |
7 |
Correct |
353 ms |
1984 KB |
Output is correct |
8 |
Correct |
373 ms |
1968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
72 ms |
980 KB |
Output is correct |
6 |
Correct |
78 ms |
1068 KB |
Output is correct |
7 |
Correct |
344 ms |
1980 KB |
Output is correct |
8 |
Correct |
361 ms |
1980 KB |
Output is correct |
9 |
Correct |
327 ms |
1896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
452 KB |
Output is correct |
4 |
Correct |
5 ms |
452 KB |
Output is correct |
5 |
Correct |
13 ms |
640 KB |
Output is correct |
6 |
Correct |
12 ms |
640 KB |
Output is correct |
7 |
Correct |
22 ms |
724 KB |
Output is correct |
8 |
Correct |
22 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
205 ms |
1532 KB |
Output is correct |
4 |
Correct |
298 ms |
1788 KB |
Output is correct |
5 |
Correct |
1225 ms |
3404 KB |
Output is correct |
6 |
Correct |
1401 ms |
3556 KB |
Output is correct |
7 |
Correct |
1436 ms |
3556 KB |
Output is correct |
8 |
Correct |
1341 ms |
3492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
472 KB |
Output is correct |
3 |
Correct |
70 ms |
984 KB |
Output is correct |
4 |
Correct |
354 ms |
1936 KB |
Output is correct |
5 |
Correct |
1470 ms |
3540 KB |
Output is correct |
6 |
Correct |
1490 ms |
3540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
317 ms |
1892 KB |
Output is correct |
6 |
Correct |
317 ms |
1876 KB |
Output is correct |
7 |
Correct |
353 ms |
1984 KB |
Output is correct |
8 |
Correct |
373 ms |
1968 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
324 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
72 ms |
980 KB |
Output is correct |
14 |
Correct |
78 ms |
1068 KB |
Output is correct |
15 |
Correct |
344 ms |
1980 KB |
Output is correct |
16 |
Correct |
361 ms |
1980 KB |
Output is correct |
17 |
Correct |
327 ms |
1896 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
3 ms |
452 KB |
Output is correct |
21 |
Correct |
5 ms |
452 KB |
Output is correct |
22 |
Correct |
13 ms |
640 KB |
Output is correct |
23 |
Correct |
12 ms |
640 KB |
Output is correct |
24 |
Correct |
22 ms |
724 KB |
Output is correct |
25 |
Correct |
22 ms |
724 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
205 ms |
1532 KB |
Output is correct |
29 |
Correct |
298 ms |
1788 KB |
Output is correct |
30 |
Correct |
1225 ms |
3404 KB |
Output is correct |
31 |
Correct |
1401 ms |
3556 KB |
Output is correct |
32 |
Correct |
1436 ms |
3556 KB |
Output is correct |
33 |
Correct |
1341 ms |
3492 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
3 ms |
472 KB |
Output is correct |
36 |
Correct |
70 ms |
984 KB |
Output is correct |
37 |
Correct |
354 ms |
1936 KB |
Output is correct |
38 |
Correct |
1470 ms |
3540 KB |
Output is correct |
39 |
Correct |
1490 ms |
3540 KB |
Output is correct |
40 |
Correct |
106 ms |
1156 KB |
Output is correct |
41 |
Correct |
350 ms |
1888 KB |
Output is correct |
42 |
Correct |
862 ms |
2776 KB |
Output is correct |
43 |
Correct |
1427 ms |
3560 KB |
Output is correct |
44 |
Correct |
1396 ms |
3560 KB |
Output is correct |
45 |
Correct |
1412 ms |
3596 KB |
Output is correct |
46 |
Correct |
348 ms |
1940 KB |
Output is correct |
47 |
Correct |
776 ms |
2772 KB |
Output is correct |
48 |
Correct |
738 ms |
2716 KB |
Output is correct |