Submission #12056

#	Time	Username	Problem	Language	Result	Execution time	Memory
12056		tncks0121	배낭 문제 준비하기 (GA9_invknapsack)	C++14	18 / 100	192 ms	2848 KiB

invknapsack

#include <iostream>
#include <cstdio>
 
using namespace std;
 
//int good[100005][305];
int chk[100005], cur[100005];
 
int p = 1;
int res[100005], rn;
// table[i][j] : 길이 j로 답이 i인 걸 만들 수 있는가?
 
void solve (int t) {
    if(cur[t] < 0) {
      if(chk[-cur[t]] < chk[t+cur[t]]) {
        solve(-cur[t]);
        solve(t + cur[t]);
      }else{
        solve(t + cur[t]);
        solve(-cur[t]);
      }
        
    }else {
        for(int i = 0; i < chk[t]; i++) {
            res[++rn] = (i < cur[t]) ? p : 293-p;
        }
        p += cur[t]*p;
    }
}
 
int main() {
    for(int i = 1; i <= 100000; i++) chk[i] = (int)1e9;
    for(int a = 1; a <= 300; a++) {
        for(int b = 1; b <= 300-a; b++) {
        //  good[a*b][a+b] = a;
            if(chk[a*b] > a+b) {
                cur[a*b] = a;
                chk[a*b] = a+b;
            }
        }
    }
    for(int i = 1; i <= 10000; i++) if(chk[i] == (int)1e9) {
        for(int j = 1; j < i; j++) {
			if(cur[j] < 0 || cur[i-j] < 0) continue;
            if(chk[i] > chk[j] + chk[i-j]) {
                cur[i] = -j;
                (chk[i] = chk[j] + chk[i-j]);
            }
        }
    }
     
    int t; scanf("%d", &t);
    solve(t);
     
    printf("%d 293\n", rn);
    for(int i = 1; i <= rn; i++) printf("%d ", res[i]);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 13 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 29
• Subtask 5: 0 / 36