Submission #818947

#	Time	Username	Problem	Language	Result	Execution time	Memory
818947		Alan	스트랩 (JOI14_straps)	C++17	55 / 100	4 ms	384 KiB

straps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[2005];
const ll inf = 1e18;

int main () {
	int n;
	cin >> n;
	vector<ll> cand {};
	for (int i = 2; i <= n; i++) dp[i] = -inf;
	ll base = 0;
	while (n--) {
		ll a, b;
		cin >> a >> b;
		if (a && b >= 0) {
			for (int i = 2000; i >= a; i--) dp[i] = dp[i-a+1];
			for (int i = 1; i < a; i++) dp[i] = 0;
			base += b;
		} else if (b >= 0) cand.push_back(b);
		else if (a > 1) for (int i = 2000; i >= a; i--) dp[i] = max(dp[i], dp[i-a+1] + b);
	}
	sort(cand.rbegin(), cand.rend());
	for (int i = 1; i < (int) cand.size(); i++) cand[i] += cand[i-1];
	ll ans = 0;
	for (int i = 0; i < (int) cand.size(); i++) ans = max(ans, dp[i+1] + cand[i]);
	cout << ans+base << '\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 45 / 45
• Subtask 4: 0 / 45