Submission #16060

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
16060	2015-08-14 04:44:56	kaTkaHr	배낭 문제 준비하기 (GA9_invknapsack)	C++98	0 / 100	1000 ms	1932 KiB

invknapsack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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()
{
  for(ll R = 1e18 - 1e7; R <= 1e18 - 1e6; 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++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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