Submission #209522

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
209522	2020-03-14 12:34:55	model_code	Knapsack (NOI18_knapsack)	C++17	37 / 100	53 ms	79484 KiB

knapsack

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
// 0-1 Knapsack (IV)
// should be MLE/TLE (too slow?)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_N 110 // actually 100
#define MAX_NK 1010 // actually 100*100 = 10000
#define MAX_S 10010 // actually 10000
int i, j, S, N, K, new_N;
ll V, W, new_V[MAX_NK], new_W[MAX_NK]; // transformed data set, can exceed the value of 32 bit signed integer!
ll memo[MAX_NK][MAX_S]; // 80 MB * 4 = 320 MB... > 256 MB
ll value(int id, int w) {
  if (id == new_N || w == 0) return 0;
  if (memo[id][w] != -1) return memo[id][w];
  if (new_W[id] > w) return memo[id][w] = value(id+1, w);
  return memo[id][w] = max(value(id+1, w), new_V[id] + value(id+1, w-new_W[id]));
}
int main() {
  // freopen("in.txt", "r", stdin);
    scanf("%d %d", &S, &N);
    // assert(1 <= S && S <= 10000);
    // assert(1 <= N && N <= 100);
    for (i = new_N = 0; i < N; i++) {
      scanf("%lld %lld %d", &V, &W, &K);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &S, &N);
     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:30:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld %lld %d", &V, &W, &K);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27