oj.uz

답안 #12078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12078 2014-12-20T23:14:01 Z ainta 배낭 문제 준비하기 (GA9_invknapsack) C++
5 / 100
 0 ms 1100 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
#define INF 1000000000000000000LL
long long K, D[320];
bool v[320];
struct A{
	int num;
	long long S;
	bool operator <(const A &p)const{
		return S < p.S;
	}
}P[320];
bool Do(int n){
	int i, C = n;
	long long S = K;
	for (i = 0; i <= 300; i++)v[i] = false;
	for (i = n; i >= 0; i--){
		if (P[i].S == -1)break;
		if (S >= P[i].S){
			S -= P[i].S;
			v[300 - P[i].num] = true;
			C++;
		}
	}
	if (!S){
		printf("%d %d\n", C, 300);
		for (i = 1; i <= n; i++)printf("1 ");
		for (i = 150; i <= 300; i++)if (v[i])printf("%d ", i);
		printf("\n");
		return true;
	}
	return false;
}
int main()
{
	int i, j, c;
	scanf("%lld", &K);
	for (i = 0; i <= 300; i++){
		for (j = i; j >= 1; j--){
			if (D[j] == -1 || D[j - 1] == -1){
				D[j] = -1;
				continue;
			}
			D[j] = D[j] + D[j - 1];
			if (D[j] > INF)D[j] = -1;
		}
		D[0] = 1;
		for (j = 0; j <= i; j++){
			P[j].S = D[j];
			P[j].num = j;
		}
		sort(P, P + i + 1);
		if (Do(i))break;
	}
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1100 KB Output is correct
2 Correct 0 ms 1100 KB Output is correct
3 Correct 0 ms 1100 KB Output is correct
4 Correct 0 ms 1100 KB Output is correct
5 Correct 0 ms 1100 KB Output is correct
6 Correct 0 ms 1100 KB Output is correct
7 Correct 0 ms 1100 KB Output is correct
8 Correct 0 ms 1100 KB Output is correct
9 Correct 0 ms 1100 KB Output is correct
10 Correct 0 ms 1100 KB Output is correct
11 Correct 0 ms 1100 KB Output is correct
12 Correct 0 ms 1100 KB Output is correct
13 Correct 0 ms 1100 KB Output is correct
14 Correct 0 ms 1100 KB Output is correct

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1100 KB Output is correct
2 Incorrect 0 ms 1096 KB Output isn't correct - wrong output format : Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -