제출 #818975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
818975		Alan	스트랩 (JOI14_straps)	C++17	55 / 100	7 ms	444 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;
	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());
	int sz = cand.size();
	for (int i = 1; i < sz; i++) cand[i] += cand[i-1];
	ll ans = 0;
	if (!cand.empty()) for (int i = 0; i < 2000; i++) ans = max(ans, dp[i+1] + cand[min(i, sz-1)]);
	cout << ans+base << '\n';
	return 0;
}

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