Submission #1297254

#TimeUsernameProblemLanguageResultExecution timeMemory
1297254EkinOnalCloud Computing (CEOI18_clo)C++20
0 / 100
151 ms327680 KiB
//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define MAX 10005
#define pb push_back
// #define mp make_pair 
#define int long long
#define f first
#define s second
#define vi vector<int>
#define pii pair<int,int>
#define si set<int>
#define vpii vector<pair<int,int>> 
const int mod = 1e9+7;
const int INF = 1e18;
// myMap.begin()->first :  key
// myMap.begin()->second : value
 
int epow(int a,int b){int ans=1;while(b){if(b&1) ans*=a;a*=a;b>>=1;ans%=mod;a%=mod;}return ans%mod;}
int gcd(int a,int b) {if(a<b)swap(a,b);while(b){int tmp=b;b=a%b;a=tmp;}return a;}
int mul(int a,int b){return ((a%mod)*(b%mod))%mod;}
int sum(int a,int b){return ((a%mod)+(b%mod))%mod;}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
// typedef
// tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;

bool comp(array<int,3>a,array<int,3>b){
	if(a[1]!=b[1]) return a[1]>b[1];
	return a[2]<b[2];
} 

void solve(){ 
	int n; cin>>n;
	vector<array<int,3>> arr;
	for(int i=1;i<=n;i++){
		int a,b,c; cin>>a>>b>>c;
		arr.pb({a,b,-c});
	}
	int m; cin>>m;
	for(int i=1;i<=m;i++){
		int a,b,c; cin>>a>>b>>c;
		arr.pb({-a,b,c});
	}	
	sort(arr.begin(),arr.end(),comp);

	int nn=arr.size();
	int dp[nn+5][50*nn+5]{};
	for(int i=0;i<=nn;i++) for(int j=0;j<=50*nn;j++) dp[i][j]=-INF;

	dp[0][0]=0;
	for(int i=1;i<=nn;i++){
		for(int j=0;j<=50*nn;j++){
			dp[i][j]=dp[i-1][j];
			if(j-arr[i-1][0]>=0 && j-arr[i-1][0]<=50*nn) dp[i][j]=max(dp[i][j], dp[i-1][j-arr[i-1][0]]+arr[i-1][2] );
		}	
	}
	int ans=0;
	for(int i=0;i<=50*nn;i++) ans=max(ans,dp[nn][i]);
	cout<<ans<<endl;

}	
	
int32_t main(/*int32_t argc, char* argv[]*/){
	std::ios_base::sync_with_stdio(0); std::cin.tie(0);		
	// freopen("exercise.in", "r", stdin);
	// freopen("exercise.out", "w", stdout);

	int t=1;
	// cin >> t;
	while (t--) solve();
 	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...