제출 #1282847

#제출 시각아이디문제언어결과실행 시간메모리
1282847Jawad_Akbar_JJCloud Computing (CEOI18_clo)C++20
100 / 100
1496 ms3748 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
int dp[2][2005][102], inf = 1e17;

signed main(){
	int n, m;
	cin>>n;

	vector<pair<int, pair<int, int>>> buy = {{0, {0, 0}}}, sell = buy;

	for (int i=1, c, f, v;i<=n;i++){
		cin>>c>>f>>v;
		buy.push_back({f, {c, v}});
	}
	cin>>m;

	for (int i=1, c, f, v;i<=m;i++){
		cin>>c>>f>>v;
		sell.push_back({f, {c, v}});
	}

	sort(rbegin(buy), rend(buy));
	sort(rbegin(sell), rend(sell));

	for (int j=0;j<=m;j++){
		for (int k=0;k<=100;k++)
			dp[0][j][k] = dp[1][j][k] = -inf;
	}

	dp[0][0][0] = 0;

	for (int i=0;i<=n;i++){
		for (int j=0;j<=m;j++){
			for (int k=99;k>=0;k--)
				dp[0][j][k] = max(dp[0][j][k], dp[0][j][k+1]);
			for (int k=0;k<=100;k++){
				dp[1][j][k] = max(dp[1][j][k], dp[0][j][k]);
				dp[0][j+1][k] = max(dp[0][j+1][k], dp[0][j][k]);

				dp[1][j][min(100LL, k + buy[i].second.first)] = max(dp[1][j][min(100LL, k + buy[i].second.first)], dp[0][j][k] - buy[i].second.second);
				
				if (k - sell[j].second.first >= 0 and i > 0 and sell[j].first <= buy[i-1].first)
					dp[0][j+1][k - sell[j].second.first] = max(dp[0][j+1][k - sell[j].second.first], dp[0][j][k] + sell[j].second.second);
			}
		}
		for (int j=0;j<=m;j++)
			for (int k=0;k<=100;k++)
				dp[0][j][k] = dp[1][j][k], dp[1][j][k] = -inf;
	}
	cout<<dp[0][m][0]<<'\n';
}
#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...