Submission #72893

#	Time	Username	Problem	Language	Result	Execution time	Memory
72893		zscoder	Cloud Computing (CEOI18_clo)	C++17	100 / 100	901 ms	2564 KiB

clo

#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 fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 111111;
ll dp[2][N];
const ll INF=ll(1e18);

void amax(ll &a, ll b)
{
	if(b>a) a=b; 
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	vector<pair<ii,ii> > vec;
	for(int i=0;i<n;i++)
	{
		int c,f,v; cin>>c>>f>>v;
		vec.pb(mp(mp(f,1),mp(c,v)));
	}
	int m; cin>>m;
	for(int i=0;i<m;i++)
	{
		int c,f,v; cin>>c>>f>>v;
		vec.pb(mp(mp(f,0),mp(c,v)));
	}
	sort(vec.rbegin(),vec.rend());
	for(int i=0;i<N;i++)
	{
		dp[0][i]=dp[1][i]=-INF;
	}
	dp[1][0] = 0;
	for(int i=0;i<vec.size();i++)
	{
		int cur=i&1; int pre=cur^1;
		int ty=vec[i].fi.se;
		int c=vec[i].se.fi;
		ll v=vec[i].se.se;
		for(int j=0;j<min(N,50*(i+2));j++)
		{
			dp[cur][j] = -INF;
		}
		for(int j=0;j<min(N,50*(i+2));j++)
		{
			if(dp[pre][j]>-INF)
			{
				ll val=dp[pre][j];
				amax(dp[cur][j], val);
				//apply operation
				if(ty) //buy
				{
					amax(dp[cur][j+c], val-v);
				}
				else
				{
					if(j>=c) amax(dp[cur][j-c],val+v);
				}
			}
		}
	}
	ll ans=0;
	for(int j=0;j<N;j++)
	{
		ans=max(ans,dp[(int(vec.size())-1)&1][j]);
	}
	cout<<ans<<'\n';
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~

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