Submission #161655

#	Time	Username	Problem	Language	Result	Execution time	Memory
161655		amoo_safar	Cloud Computing (CEOI18_clo)	C++14	100 / 100	775 ms	2424 KiB

clo

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 2e3 + 10;
const ll INF = (ll) (LONG_LONG_MAX - 3ll) / 2ll;
const ll MAXC = MAXN * 50;

inline ll mul(ll a, ll b){
	return (a * b) % MOD;
}

inline ll pw(ll b, ll p){
	if(p == 0) return 1;
	if(p & 1) return mul(b, pw(b, p - 1));
	return pw(mul(b,b), p / 2);
}

ll dp[2][MAXC];

struct obj{
	ll f, v, c, t;
};

bool CMP(obj a, obj b){
	if(a.f == b.f) return a.t < b.t;
	return a.f > b.f;
}
vector<obj> A;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < 2; i++) fill(dp[i], dp[i] + MAXC, -INF);
	ll n, m;
	cin >> n;
	obj x;
	for(int i = 0; i < n;i++){
		x.t = 0;
		cin >> x.c >> x.f >> x.v;
		A.pb(x);
	}
	cin >> m;
	for(int i = 0; i < m; i++){
		x.t = 1;
		cin >> x.c >> x.f >> x.v;
		A.pb(x);
	}
	sort(all(A), CMP);
	ll N = A.size();
	dp[1][0] = 0;
	for(int i = 0; i < N; i++){
		int ii = i & 1;
		if(A[i].t == 0){
			for(int j = 0; j < MAXC; j++){
				dp[ii][j] = dp[ii ^ 1][j];
				if(j >= A[i].c) dp[ii][j] = max(dp[ii][j], dp[ii ^ 1][j - A[i].c] - A[i].v);
			}
		} else {
			for(int j = 0; j < MAXC; j++){
				dp[ii][j] = dp[ii ^ 1][j];
				if(j + A[i].c < MAXC) dp[ii][j] = max(dp[ii][j], dp[ii ^ 1][j + A[i].c] + A[i].v);
			}
		}
	}
	cout << *max_element(dp[((N - 1) & 1)], dp[((N - 1) & 1)] + MAXC);
	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