oj.uz

Submission #481081

# Submission time Handle Problem Language Result Execution time Memory
481081 2021-10-19T12:37:39 Z chuangsheep Knapsack (NOI18_knapsack) C++11
100 / 100
 135 ms 125764 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#define allr(x, r) begin(x), begin(x) + (r)
#define mp make_pair

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

int main()
{
#if defined(DEBUG) && !defined(ONLINE_JUDGE)
  // DEBUG
  cerr << "DEBUG flag set - see test.out for output\n";
  freopen("/home/chuang/shared-drives/F:/repos/cp/ois/noi2018/test.in", "r", stdin);
  freopen("/home/chuang/shared-drives/F:/repos/cp/ois/noi2018/test.out", "w", stdout);
#else
  cin.tie(0)->sync_with_stdio(false);
#endif

  int S, N;
  cin >> S >> N;

  vector<vector<pi>> items(S + 1, vector<pi>());

  for (int i = 0; i < N; i++)
  {
    int V, W, K;
    cin >> V >> W >> K;
    items[W].push_back({V, K});
  }

  for (int i = 0; i <= S; i++)
    sort(all(items[i]), greater<pi>());

  int total = 0;
  for (int i = 1; i <= S; i++)
    total += S / i;

  vector<vi> dp(total + 1, vi(S + 1, 0));
  int n_i = 1;
  for (int w = 1; w <= S; w++)
  {
    if (items[w].size() == 0)
      continue;
    int w_i = 0, w_c = items[w][0].second;
    for (int num = 0; num < S / w; num++)
    {
      for (int c = 1; c <= S; c++)
      {
        dp[n_i][c] = dp[n_i - 1][c];
        if (c - w >= 0)
          dp[n_i][c] = max(dp[n_i][c], dp[n_i - 1][c - w] + items[w][w_i].first);
      }
      n_i++;
      w_c--;
      if (w_c == 0)
      {
        w_i++;
        if (w_i >= items[w].size())
          break;
        w_c = items[w][w_i].second;
      }
    }
  }

  cout << dp[n_i - 1][S] << "\n";

  return 0;
}

Compilation message

knapsack.cpp: In function 'int main()':
knapsack.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (w_i >= items[w].size())
      |             ~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44156 KB Output is correct
2 Correct 23 ms 44044 KB Output is correct
3 Correct 20 ms 44088 KB Output is correct
4 Correct 19 ms 44056 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 55 ms 122436 KB Output is correct
3 Correct 51 ms 122268 KB Output is correct
4 Correct 51 ms 121800 KB Output is correct
5 Correct 53 ms 121796 KB Output is correct
6 Correct 55 ms 122436 KB Output is correct
7 Correct 54 ms 122180 KB Output is correct
8 Correct 58 ms 121840 KB Output is correct
9 Correct 51 ms 121820 KB Output is correct
10 Correct 57 ms 122196 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 55 ms 122436 KB Output is correct
3 Correct 51 ms 122268 KB Output is correct
4 Correct 51 ms 121800 KB Output is correct
5 Correct 53 ms 121796 KB Output is correct
6 Correct 55 ms 122436 KB Output is correct
7 Correct 54 ms 122180 KB Output is correct
8 Correct 58 ms 121840 KB Output is correct
9 Correct 51 ms 121820 KB Output is correct
10 Correct 57 ms 122196 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 53 ms 122328 KB Output is correct
13 Correct 52 ms 122272 KB Output is correct
14 Correct 56 ms 122436 KB Output is correct
15 Correct 52 ms 121796 KB Output is correct
16 Correct 56 ms 122180 KB Output is correct
17 Correct 54 ms 121936 KB Output is correct
18 Correct 55 ms 122260 KB Output is correct
19 Correct 56 ms 122436 KB Output is correct
20 Correct 52 ms 121828 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44156 KB Output is correct
2 Correct 23 ms 44044 KB Output is correct
3 Correct 20 ms 44088 KB Output is correct
4 Correct 19 ms 44056 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 55 ms 122436 KB Output is correct
7 Correct 51 ms 122268 KB Output is correct
8 Correct 51 ms 121800 KB Output is correct
9 Correct 53 ms 121796 KB Output is correct
10 Correct 55 ms 122436 KB Output is correct
11 Correct 54 ms 122180 KB Output is correct
12 Correct 58 ms 121840 KB Output is correct
13 Correct 51 ms 121820 KB Output is correct
14 Correct 57 ms 122196 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 53 ms 122328 KB Output is correct
17 Correct 52 ms 122272 KB Output is correct
18 Correct 56 ms 122436 KB Output is correct
19 Correct 52 ms 121796 KB Output is correct
20 Correct 56 ms 122180 KB Output is correct
21 Correct 54 ms 121936 KB Output is correct
22 Correct 55 ms 122260 KB Output is correct
23 Correct 56 ms 122436 KB Output is correct
24 Correct 52 ms 121828 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 58 ms 122256 KB Output is correct
27 Correct 59 ms 122444 KB Output is correct
28 Correct 54 ms 122244 KB Output is correct
29 Correct 56 ms 122232 KB Output is correct
30 Correct 54 ms 122176 KB Output is correct
31 Correct 57 ms 122220 KB Output is correct
32 Correct 52 ms 122248 KB Output is correct
33 Correct 56 ms 121796 KB Output is correct
34 Correct 52 ms 122180 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44156 KB Output is correct
2 Correct 23 ms 44044 KB Output is correct
3 Correct 20 ms 44088 KB Output is correct
4 Correct 19 ms 44056 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 55 ms 122436 KB Output is correct
7 Correct 51 ms 122268 KB Output is correct
8 Correct 51 ms 121800 KB Output is correct
9 Correct 53 ms 121796 KB Output is correct
10 Correct 55 ms 122436 KB Output is correct
11 Correct 54 ms 122180 KB Output is correct
12 Correct 58 ms 121840 KB Output is correct
13 Correct 51 ms 121820 KB Output is correct
14 Correct 57 ms 122196 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 53 ms 122328 KB Output is correct
17 Correct 52 ms 122272 KB Output is correct
18 Correct 56 ms 122436 KB Output is correct
19 Correct 52 ms 121796 KB Output is correct
20 Correct 56 ms 122180 KB Output is correct
21 Correct 54 ms 121936 KB Output is correct
22 Correct 55 ms 122260 KB Output is correct
23 Correct 56 ms 122436 KB Output is correct
24 Correct 52 ms 121828 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 58 ms 122256 KB Output is correct
27 Correct 59 ms 122444 KB Output is correct
28 Correct 54 ms 122244 KB Output is correct
29 Correct 56 ms 122232 KB Output is correct
30 Correct 54 ms 122176 KB Output is correct
31 Correct 57 ms 122220 KB Output is correct
32 Correct 52 ms 122248 KB Output is correct
33 Correct 56 ms 121796 KB Output is correct
34 Correct 52 ms 122180 KB Output is correct
35 Correct 34 ms 2240 KB Output is correct
36 Correct 92 ms 124300 KB Output is correct
37 Correct 93 ms 124204 KB Output is correct
38 Correct 89 ms 124496 KB Output is correct
39 Correct 92 ms 124724 KB Output is correct
40 Correct 135 ms 125468 KB Output is correct
41 Correct 116 ms 124708 KB Output is correct
42 Correct 120 ms 124744 KB Output is correct
43 Correct 132 ms 124816 KB Output is correct
44 Correct 132 ms 124484 KB Output is correct
45 Correct 88 ms 125764 KB Output is correct
46 Correct 87 ms 125100 KB Output is correct
47 Correct 99 ms 125736 KB Output is correct
48 Correct 120 ms 125636 KB Output is correct
49 Correct 86 ms 125308 KB Output is correct
50 Correct 111 ms 125252 KB Output is correct