Submission #448172

#	Time	Username	Problem	Language	Result	Execution time	Memory
448172		Dirii	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1972 ms	3596 KiB

clo

#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 ;
}

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