Submission #906410

#	Time	Username	Problem	Language	Result	Execution time	Memory
906410		Nonoze	Cloud Computing (CEOI18_clo)	C++17	0 / 100	1 ms	604 KiB

clo

#include <bits/stdc++.h>

#define int long long
#define sz(x) (int)(x.size())

using namespace std;

struct computer {
	int c, f, v;
	bool operator <(const computer &a) {
		if (f>a.f) return true;
		else if (f==a.f) return v<a.v;
		return false;
	}
};

int n, m;
vector<computer> a;
map<pair<int, int>, int> memo;

int dp(int i, int cores) {
	if (cores<0) return -1000000000;
	if (i>=n) return (a[i].c<0&&cores+a[i].c>=0)?a[i].v: 0;
	if (memo.count({i, cores})) return memo[{i, cores}];
	int ans=dp(i+1, cores);
	if (cores+a[i].c>=0) ans=max(ans, dp(i+1, cores+a[i].c)+a[i].v);
	return memo[{i, cores}]=ans;
}

void solve() {
	cin >> n;
	a.clear();
	a.resize(n);
	for (auto &u: a) {
		cin >> u.c >> u.f >> u.v;
		u.v*=-1;
	}
	cin >> m;
	for (int i=0; i<m; i++) {
		int c, f, v; cin >> c >> f >> v;
		c*=-1;
		a.push_back({c, f, v});
	}
	sort(a.begin(), a.end());
	int fin=n+m;
	vector<int> dp(50*n, -1e15);
	vector<int> lst(50*n, -1e15);
	lst[0]=0;
	dp[0]=0;
	for (int tt=0; tt<n+m; tt++) {
		for (int i=max(0LL, min(0LL, a[tt].c)); i<50*n; i++) {
			if (i+a[tt].c>=50*n) continue;
			dp[i+a[tt].c]=max(lst[i+a[tt].c], lst[i]+a[tt].v);
		}
		lst=dp;
	}
	cout << *max_element(dp.begin(), dp.end()) << endl;
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

Compilation message (stderr)

clo.cpp: In function 'void solve()':
clo.cpp:45:6: warning: unused variable 'fin' [-Wunused-variable]
   45 |  int fin=n+m;
      |      ^~~

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