제출 #1124150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124150		jitic22514	Cloud Computing (CEOI18_clo)	C++17	18 / 100	385 ms	327680 KiB

clo

//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn = 2e3 + 5;
const ll inf = 1e17;
const int maxk = 56;

template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}
template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}

struct computer{
	int core,flow,price;
	bool operator <(const computer&other) const{
		return (flow < other.flow);
	}
};
struct order{
	int C,F,V;
	bool operator <(const order&other) const{
		return (F < other.F);
	}
};

ll dp[maxn][maxn][maxk];
ll f[maxn][maxk];

computer a[maxn];
order b[maxn];

void input(int &n,int &m){
	cin >> n;
	for (int i = 1 ; i <= n ; i++) cin >> a[i].core >> a[i].flow >> a[i].price;
	cin >> m;
	for (int i = 1 ; i <= m ; i++) cin >> b[i].C >> b[i].F >> b[i].V;
}

void perform_dp(int i,int n,int m){
	int cap = a[i].core;
	
	for (int j = m ; j > 0 ; j--){
		if (a[i].flow < b[j].F) continue;
		
		int bC = b[j].C,bV = b[j].V;
		
		//classic cases:
		for (int k = 0 ; k <= cap ; k++)
		    maxi(dp[i][j][k],dp[i][j + 1][k]);
		
		for (int k = bC ; k <= cap ; k++)
		    maxi(dp[i][j][k],dp[i][j + 1][k - bC] + bV);
		///
		
		//new case: partialy bought order
		for (int k = 0 ; k <= bC ; k++){
			int t = bC - k;
			
			if (t <= cap)
			   maxi(dp[i][j][t],f[j][k] + bV);
		}
	}
	
	for (int j = 0 ; j <= m + 1 ; j++)
	  for (int k = 0 ; k <= cap + 1 ; k++)
	    dp[i][j][k] -= a[i].price;
	
	//propagate to new case
	for (int j = m ; j > 0 ; j--){
		if (a[i].flow < b[j].F) continue;
		
		int bC = b[j].C;
		
		//k : i'm going to buy
		for (int k = 0 ; k <= min(bC,cap) ; k++){
			maxi(f[j][k],dp[i][j + 1][cap - k]);
		}
	}
}

void remf(int m){
	for (int i = 0 ; i <= m + 2 ; i++)
	   for (int j = 0 ; j <= 51 ; j++)
	     f[i][j] = -inf;
}

ll solve(int n,int m){
	sort(a + 1,a + 1 + n);
	sort(b + 1,b + 1 + m);
	
	remf(m);
	
	for (int i = n ; i > 0 ; i--)
	   perform_dp(i,n,m);
	
	ll res = 0;
	for (int i = 1 ; i <= n ; i++)
	    for (int j = 1 ; j <= m ; j++)
	        for (int k = 0 ; k <= 50 ; k++)
	           maxi(res,dp[i][j][k]);
	
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
// 	freopen("COMPUTING.inp","r",stdin);
// 	freopen("COMPUTING.out","w",stdout);
	
	int n,m;
	input(n,m);
	
	cout << solve(n,m);
	
	return 0;
}

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