Submission #16062

#TimeUsernameProblemLanguageResultExecution timeMemory
16062kaTkaHr배낭 문제 준비하기 (GA9_invknapsack)C++14
100 / 100
0 ms1936 KiB
#include<stdio.h> #include<vector> using namespace std; typedef long long ll; ll D[305][305]; int K = 300; vector<int> L; void add(int x) { int s = L.size(), e = s + 1; for (int i = 0; i <= K; i++) D[e][i] = D[s][i]; for (int i = x; i <= K; i++) D[e][i] += D[s][i-x]; L.push_back(x); } int main() { ll R; scanf("%lld", &R); D[0][0] = 1; for(int i = 1; i <= K; i *= 2){ add(i); } while(D[L.size()][K] + D[L.size()][K-1] <= R) add(1); while(D[L.size()][K] != R){ for(int j = 1; j <= K; j++){ if(D[L.size()][K] + D[L.size()][K-j] <= R ){ add(j); break; } } } printf("%d %d\n", L.size(), K); for(int c : L) printf("%d ", c); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...