oj.uz

Submission #6063

# Submission time Handle Problem Language Result Execution time Memory
6063 2014-06-17T02:49:35 Z ainta 스트랩 (JOI14_straps) C++
100 / 100
 4 ms 1104 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 0 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 0 ms 1104 KB Output is correct
5 Correct 0 ms 1104 KB Output is correct
6 Correct 0 ms 1104 KB Output is correct
7 Correct 0 ms 1104 KB Output is correct
8 Correct 0 ms 1104 KB Output is correct
9 Correct 0 ms 1104 KB Output is correct
10 Correct 0 ms 1104 KB Output is correct
11 Correct 0 ms 1104 KB Output is correct
12 Correct 0 ms 1104 KB Output is correct
13 Correct 0 ms 1104 KB Output is correct
14 Correct 0 ms 1104 KB Output is correct
15 Correct 0 ms 1104 KB Output is correct
16 Correct 0 ms 1104 KB Output is correct
17 Correct 0 ms 1104 KB Output is correct
18 Correct 0 ms 1104 KB Output is correct
19 Correct 0 ms 1104 KB Output is correct
20 Correct 0 ms 1104 KB Output is correct
21 Correct 0 ms 1104 KB Output is correct
22 Correct 0 ms 1104 KB Output is correct
23 Correct 0 ms 1104 KB Output is correct
24 Correct 0 ms 1104 KB Output is correct
25 Correct 0 ms 1104 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 0 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 0 ms 1104 KB Output is correct
5 Correct 0 ms 1104 KB Output is correct
6 Correct 0 ms 1104 KB Output is correct
7 Correct 0 ms 1104 KB Output is correct
8 Correct 0 ms 1104 KB Output is correct
9 Correct 0 ms 1104 KB Output is correct
10 Correct 0 ms 1104 KB Output is correct
11 Correct 0 ms 1104 KB Output is correct
12 Correct 0 ms 1104 KB Output is correct
13 Correct 0 ms 1104 KB Output is correct
14 Correct 0 ms 1104 KB Output is correct
15 Correct 0 ms 1104 KB Output is correct
16 Correct 0 ms 1104 KB Output is correct
17 Correct 0 ms 1104 KB Output is correct
18 Correct 0 ms 1104 KB Output is correct
19 Correct 0 ms 1104 KB Output is correct
20 Correct 0 ms 1104 KB Output is correct
21 Correct 0 ms 1104 KB Output is correct
22 Correct 0 ms 1104 KB Output is correct
23 Correct 0 ms 1104 KB Output is correct
24 Correct 0 ms 1104 KB Output is correct
25 Correct 0 ms 1104 KB Output is correct
26 Correct 0 ms 1104 KB Output is correct
27 Correct 0 ms 1104 KB Output is correct
28 Correct 0 ms 1104 KB Output is correct
29 Correct 0 ms 1104 KB Output is correct
30 Correct 0 ms 1104 KB Output is correct
31 Correct 0 ms 1104 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 0 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 0 ms 1104 KB Output is correct
5 Correct 0 ms 1104 KB Output is correct
6 Correct 0 ms 1104 KB Output is correct
7 Correct 0 ms 1104 KB Output is correct
8 Correct 0 ms 1104 KB Output is correct
9 Correct 0 ms 1104 KB Output is correct
10 Correct 0 ms 1104 KB Output is correct
11 Correct 0 ms 1104 KB Output is correct
12 Correct 0 ms 1104 KB Output is correct
13 Correct 0 ms 1104 KB Output is correct
14 Correct 0 ms 1104 KB Output is correct
15 Correct 0 ms 1104 KB Output is correct
16 Correct 0 ms 1104 KB Output is correct
17 Correct 0 ms 1104 KB Output is correct
18 Correct 0 ms 1104 KB Output is correct
19 Correct 0 ms 1104 KB Output is correct
20 Correct 0 ms 1104 KB Output is correct
21 Correct 0 ms 1104 KB Output is correct
22 Correct 0 ms 1104 KB Output is correct
23 Correct 0 ms 1104 KB Output is correct
24 Correct 0 ms 1104 KB Output is correct
25 Correct 0 ms 1104 KB Output is correct
26 Correct 0 ms 1104 KB Output is correct
27 Correct 0 ms 1104 KB Output is correct
28 Correct 0 ms 1104 KB Output is correct
29 Correct 0 ms 1104 KB Output is correct
30 Correct 0 ms 1104 KB Output is correct
31 Correct 0 ms 1104 KB Output is correct
32 Correct 0 ms 1104 KB Output is correct
33 Correct 4 ms 1104 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 0 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 0 ms 1104 KB Output is correct
5 Correct 0 ms 1104 KB Output is correct
6 Correct 0 ms 1104 KB Output is correct
7 Correct 0 ms 1104 KB Output is correct
8 Correct 0 ms 1104 KB Output is correct
9 Correct 0 ms 1104 KB Output is correct
10 Correct 0 ms 1104 KB Output is correct
11 Correct 0 ms 1104 KB Output is correct
12 Correct 0 ms 1104 KB Output is correct
13 Correct 0 ms 1104 KB Output is correct
14 Correct 0 ms 1104 KB Output is correct
15 Correct 0 ms 1104 KB Output is correct
16 Correct 0 ms 1104 KB Output is correct
17 Correct 0 ms 1104 KB Output is correct
18 Correct 0 ms 1104 KB Output is correct
19 Correct 0 ms 1104 KB Output is correct
20 Correct 0 ms 1104 KB Output is correct
21 Correct 4 ms 1104 KB Output is correct
22 Correct 4 ms 1104 KB Output is correct
23 Correct 0 ms 1104 KB Output is correct
24 Correct 4 ms 1104 KB Output is correct
25 Correct 0 ms 1104 KB Output is correct