Submission #947517

#	Time	Username	Problem	Language	Result	Execution time	Memory
947517		Minbaev	Cloud Computing (CEOI18_clo)	C++17	100 / 100	285 ms	1624 KiB

clo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define int long long
#define s second
#define pii pair<int,int>

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
 
const int N=1e6 + 5	;
const int inf = 1e18 + 7;
const int mod = 998244353;
 
int cnt = 0;
int n,m,k;

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

void solve(){
	
	cin >> n;
	
	vector<array<int,4>>v;
	
	for(int i = 1;i<=n;i++){
		int a,b,c,d;
		cin >>a >> b >> c;
		d = 1;
		v.pb({a,b,c,d});
	}
	
	cin >> m;
	
	for(int i = 1;i<=m;i++){
		int a,b,c,d;
		cin >> a >> b >> c;
		d = 0;
		v.pb({a,b,c,d});
	}
	
	sort(all(v),comp);
	
	vector<int>dp(100005,-inf);
	dp[0] = 0;
	//~ cout<<v[1][0]<<" "<<v[1][1]<<" "<<v[1][2]<<" "<<v[1][3]<<"\n";
	
	int cnt = 0;
	
	for(auto to:v){
		if(to[3] == 0){
			for(int i = 0;i + to[0] <=100000;i++){
				umax(dp[i],dp[i+to[0]]+to[2]);
			}
		}
		else {
			for(int i = 100000;i>=to[0];i--){
				umax(dp[i],dp[i-to[0]]-to[2]);
			}
		}
	}
	int ans = 0;
	
	for(int i = 0;i<=100000;i++){
		umax(ans, dp[i]);
	}
	
	cout<<ans<<"\n";
}
/*
 
*/
signed main()
{	
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt>>n;
	while(tt--)solve();
 
}

Compilation message (stderr)

clo.cpp: In function 'void solve()':
clo.cpp:61:6: warning: unused variable 'cnt' [-Wunused-variable]
   61 |  int cnt = 0;
      |      ^~~

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10