#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<long long,pair<long long ,long long >>>v;
const int M=50*2001;
long long d[2][M+10];
const long long inf=1e15;
void solve()
{
long long last=0;
for(int i=0;i<M-1;i++)d[0][i]=-inf;
d[0][0]=0;
if (v[0].second.first>0)d[0][v[0].second.first]=v[0].second.second;
for(int i=1;i<n;i++)
{
for(long long j=0;j<M-1;j++)
{
d[i%2][j]=max(d[(i+1)%2][j],-inf);
if (j+v[i].second.first>0)
d[i%2][j]=max(d[i%2][j],d[(i+1)%2][j+v[i].second.first]+v[i].second.second);
last=max(d[i%2][j],last);
}
}
cout<< last;
}
int main()
{
cin>>n;
int x,y,z;
for(int i=0;i<n;i++)
{
cin>>x>>y>>z;
v.push_back({y,{x,-z}});
}
cin>>m;
for(int i=0;i<m;i++)
{
cin>>x>>y>>z;
v.push_back({y,{-x,+z}});
}
n+=m;
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1900 KB |
Output is correct |
2 |
Correct |
3 ms |
1916 KB |
Output is correct |
3 |
Incorrect |
29 ms |
1912 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
1912 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
1912 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1912 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1900 KB |
Output is correct |
2 |
Correct |
3 ms |
1916 KB |
Output is correct |
3 |
Incorrect |
29 ms |
1912 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |