Submission #383243

#	Time	Username	Problem	Language	Result	Execution time	Memory
383243		maximath_1	Cloud Computing (CEOI18_clo)	C++11	100 / 100	651 ms	2156 KiB

clo

#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 100005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
 
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}

int n, m;
pair<int, pair<int, int> > a[MX];
ll dp[2][MX];

int main(){
	cin(n);
	for(int i = 1; i <= n; i ++){
		cin(a[i].second.first); cin(a[i].first); cin(a[i].second.second);
		a[i].second.second *= -1;
	}
	cin(m);
	for(int i = n + 1; i <= n + m; i ++){
		cin(a[i].second.first); cin(a[i].first); cin(a[i].second.second);
		a[i].second.first *= -1;
	}

	sort(a + 1, a + n + m + 1, [&](pair<int, pair<int, int> > x, pair<int, pair<int, int> > y){
		if(x.first == y.first) return x.second.first > y.second.first;
		return x.first > y.first;
	});

	for(int i = 0; i < MX; i ++) dp[0][i] = -mod * 1ll * mod;
	dp[0][0] = 0;
	for(int i = 1; i <= n + m; i ++){
		int nw = i % 2, bf = 1 - nw;

		for(int j = 0; j < MX; j ++){
			dp[nw][j] = dp[bf][j];
			if(0 <= j - a[i].second.first && j - a[i].second.first < MX)
				dp[nw][j] = max(dp[nw][j], dp[bf][j - a[i].second.first] + a[i].second.second);
		}
	}

	ll ans = -mod * 1ll * mod;
	for(int j = 0; j < MX; j ++)
		ans = max(ans, dp[(n + m) % 2][j]);
	printf("%lld\n", ans);
	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