Submission #18804

#	Time	Username	Problem	Language	Result	Execution time	Memory
18804		choyi0521	스트랩 (JOI14_straps)	C++14	100 / 100	40 ms	32380 KiB

straps

#include<stdio.h>
#include<algorithm>
using namespace std;
long long dp[2001][2001];
int n;
pair<int, int> p[2000];
int main() {
	scanf("%d", &n);
	fill(&dp[0][2], &dp[n][n + 1], -1e10);
	for (int i = 0; i <n; i++) scanf("%d %d", &p[i].first, &p[i].second);
	sort(p, p + n);
	for (int i = 1; i<=n; i++){
		int a = p[n - i].first, b = p[n - i].second;
		for (int j = 0; j <= n; j++){
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			if (j + a - 1 >= 0 && j + a - 1 <= n)
				dp[i][j + a - 1] = max(dp[i][j + a - 1], dp[i - 1][j] + b);
		}
		for (int j = n - 1; j >= 0; j--)
			dp[i][j] = max(dp[i][j], dp[i][j + 1]);
	}
	printf("%lld", dp[n][0]);
	return 0;
}

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