oj.uz

Submission #12175

# Submission time Handle Problem Language Result Execution time Memory
12175 2014-12-21T15:07:10 Z imsifile 배낭 문제 준비하기 (GA9_invknapsack) C++
100 / 100
 0 ms 1092 KB 
#include<stdio.h>
#define maxn 300

typedef long long lld;

lld t, dy[303], mx;
int mi, ba[303], n;

int main(){
	int i, j, a;
	dy[0]=1;
	scanf("%lld", &t);
	if(t==1){
		printf("1 1\n1");
		return 0;
	}
	for(i=0;; i++){
		mx=0, mi=0;
		for(j=0; j<=maxn; j++){
			if(mx<dy[j] && dy[j]<=t)mx=dy[j];
			if(mx==dy[j])mi=j;
		}
		if(mx==t)break;
		if(mi==0)a=1;
		else{
			for(a=1; a<=mi; a++){
				if(dy[mi]+dy[mi-a]<=t)break;
			}
		}
		ba[i]=a;
		for(j=maxn; j>=a; j--){
			if(dy[j]<=t)dy[j]+=dy[j-a];
		}
	}
	n=i;
	printf("%d %d\n", n, mi);
	for(i=0; i<n; i++)printf("%d ", ba[i]);
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1092 KB Output is correct
2 Correct 0 ms 1092 KB Output is correct
3 Correct 0 ms 1092 KB Output is correct
4 Correct 0 ms 1092 KB Output is correct
5 Correct 0 ms 1092 KB Output is correct
6 Correct 0 ms 1092 KB Output is correct
7 Correct 0 ms 1092 KB Output is correct
8 Correct 0 ms 1092 KB Output is correct
9 Correct 0 ms 1092 KB Output is correct
10 Correct 0 ms 1092 KB Output is correct
11 Correct 0 ms 1092 KB Output is correct
12 Correct 0 ms 1092 KB Output is correct
13 Correct 0 ms 1092 KB Output is correct
14 Correct 0 ms 1092 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
29.0 / 29.0

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

Subtask #5
36.0 / 36.0

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