Submission #12078

#	Time	Username	Problem	Language	Result	Execution time	Memory
12078		ainta	배낭 문제 준비하기 (GA9_invknapsack)	C++98	5 / 100	0 ms	1100 KiB

invknapsack

#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 / 5
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 29
• Subtask 5: 0 / 36