Submission #6063

#	Time	Username	Problem	Language	Result	Execution time	Memory
6063		ainta	스트랩 (JOI14_straps)	C++98	100 / 100	4 ms	1104 KiB

straps

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, w[2010], Res, Sum, S, m, Sr;
int D[2010];
int main()
{
	int i, a, b, j, x;
	scanf("%d", &n);
	for (i = 1; i < n; i++)D[i] = -2100000000;
	S++;
	for (i = 1; i <= n; i++){
		scanf("%d%d", &a, &b);
		if (!a)w[++m] = b;
		else{
			if (b >= 0){
				Sum += b;
				S += a - 1;
				continue;
			}
			x = a - 1;
			for (j = n - 1; j >= 0; j--){
				if (j + x < n && D[j + x] < D[j] + b)D[j + x] = D[j] + b;
			}
		}
	}
	for (i = n-2; i >=0; i--){
		if (D[i] < D[i + 1])D[i] = D[i + 1];
	}
	sort(w + 1, w + m + 1);
	Res = Sum;
	for (j = 1; j <= m; j++){
		Sr += w[m - j + 1];
		if (S >= j){
			if (Res < Sr + Sum)Res = Sr + Sum;
		}
		else{
			if (Res < Sr + D[j - S] + Sum) Res = Sr + D[j - S] + Sum;
		}
	}
	printf("%d\n", Res);
}

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