oj.uz

Submission #25557

# Submission time Handle Problem Language Result Execution time Memory
25557 2017-06-23T04:52:47 Z 서규호(#1074) 스트랩 (JOI14_straps) C++14
100 / 100
 3 ms 2064 KB 
#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define INF 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,rear,ans;
int d1[2002],d2[2002];
struct data{
	int x,y;
}a[2002],b[2002];

int main(){
	int cnt = 1;
	scanf("%d",&rear);
	for(int i=1; i<=rear; i++){
		int x,y;
		scanf("%d %d",&x,&y);
		if(y > 0){
			if(x > 0){
				cnt += (x-1);
				ans += y;
			}else{
				N++;
				a[N].x = x; a[N].y = y;
			}
		}else if(x > 1){
			M++;
			b[M].x = x-1; b[M].y = y;
		}
	}
	sort(a+1,a+N+1,[&](data &x,data &y){
		return x.y < y.y;
	});
	for(int i=N; i>=max(N-cnt+1,1); i--){
		ans += a[i].y;
	}
	N = max(N-cnt+1,1)-1;
	reverse(a+1,a+N+1);
	for(int i=1; i<=N; i++){
		d1[i] = d1[i-1]+a[i].y;
	}
	for(int i=1; i<=2000; i++) d2[i] = -INF;
	for(int i=1; i<=M; i++){
		for(int j=2000-b[i].x; j>=0; j--){
			if(d2[j] == -INF) continue;
			d2[j+b[i].x] = max(d2[j+b[i].x],d2[j]+b[i].y);
		}
	}
	for(int i=2000-1; i>=1; i--) d2[i] = max(d2[i],d2[i+1]);
	int big = 0;
	for(int i=1; i<=N; i++) big = max(big,d1[i]+d2[i]);
	ans += big;
	printf("%d\n",ans);

	return 0;
}

Compilation message

straps.cpp: In function 'int main()':
straps.cpp:24:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&rear);
                   ^
straps.cpp:27:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
45.0 / 45.0

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

Subtask #4
45.0 / 45.0

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