Submission #818999

#	Time	Username	Problem	Language	Result	Execution time	Memory
818999		Alan	스트랩 (JOI14_straps)	C++17	100 / 100	8 ms	360 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 <= 2000; i++) dp[i] = -inf;
	while (n--) {
		int a, b;
		cin >> a >> b;
		if (a) for (int i = 2000; i > 0; i--) dp[i] = max(dp[i], dp[max(0, i-a)+1] + b);
		else if (b >= 0) cand.push_back(b);
	}
	sort(cand.rbegin(), cand.rend());
	int sz = cand.size();
	for (int i = 1; i < sz; i++) cand[i] += cand[i-1];
	ll ans = *max_element(dp, dp+2001);
	if (!cand.empty()) for (int i = 0; i < 2000; i++) ans = max(ans, dp[i+1] + cand[min(i, sz-1)]);
	cout << ans << '\n';
	return 0;
}

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