제출 #789254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789254		parsadox2	Cloud Computing (CEOI18_clo)	C++17	100 / 100	613 ms	2164 KiB

clo

#include <bits/stdc++.h>

using namespace std;

#define int long long 
const int maxn = 2e3 + 10 , maxc = 55;
int n , m;
long long dp[2][maxn][maxc];
struct nod{
	int c , f , v;
} serv[maxn] , cust[maxn];

bool cmp(nod a , nod b)
{
	return a.f < b.f;
}

signed main()
{
	cin >> n;
	for(int i = 1 ; i <= n ; i++)  
		cin >> serv[i].c >> serv[i].f >> serv[i].v;
	cin >> m;
	for(int i = 1 ; i <= m ; i++)
		cin >> cust[i].c >> cust[i].f >> cust[i].v;
	sort(serv + 1 , serv + n + 1 , cmp);
	sort(cust + 1 , cust + m + 1 , cmp);
	int to = 1 , from = 0;
	for(int i = 1 ; i <= m ; i++)
	{
		for(int j = 0 ; j < maxc ; j++)
		{
			dp[0][i][j] = dp[0][i - 1][j];
			if(j >= cust[i].c)
				dp[0][i][j] = max(dp[0][i][j] , dp[0][i - 1][j - cust[i].c] + cust[i].v);
		}
	}
	for(int s = 1 ; s <= n ; s++)
	{
		for(int i = 1 ; i <= m ; i++)  for(int j = 0 ; j < maxc ; j++)
		{
			dp[to][i][j] = dp[to][i - 1][j];
			if(j >= cust[i].c)
				dp[to][i][j] = max(dp[to][i][j] , dp[to][i - 1][j - cust[i].c] + cust[i].v);
			else
			{
				dp[to][i][j] = max(dp[to][i][j] , dp[from][i][j]);
				if(serv[s].f >= cust[i].f)
				{
					int tmp = j + serv[s].c;
					if(tmp >= cust[i].c)
						dp[to][i][j] = max(dp[to][i][j] , dp[from][i - 1][tmp - cust[i].c] + cust[i].v - serv[s].v);
					else
						dp[to][i][j] = max(dp[to][i][j] , dp[from][i][tmp] - serv[s].v);
				}
			}
		}
		swap(from , to);
	}
	cout << dp[from][m][0] << endl;
	return 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