Submission #818987

#TimeUsernameProblemLanguageResultExecution timeMemory
818987Alan스트랩 (JOI14_straps)C++17
0 / 100
7 ms444 KiB
#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 = 0;
	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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...