Submission #12175

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

invknapsack

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