oj.uz

Submission #321846

# Submission time Handle Problem Language Result Execution time Memory
321846 2020-11-13T12:49:13 Z Pety Jelly Flavours (IOI20_jelly) C++14
0 / 100
 159 ms 155244 KB 
#include <bits/stdc++.h>
#include "jelly.h"

using namespace std;

int n, m, dp[2002][10002], dp2[2002][10002], mn[2002];

struct meh {
  int a, b, i;
} obj[2002];

bool cmp (meh a, meh b) {
  return a.a < b.a;
}

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
  int n = a.size();
  int ans = 0;
  for (int i = 0; i < n; i++)
    obj[i + 1] = {a[i], b[i], i};
  sort(obj + 1, obj + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
     mn[i] = 2e9;
    for (int j = 0; j <= x;j++) {
      dp[i][j] = 2e9;
      dp[i][j] = min(dp[i][j], dp[i - 1][j] + obj[i].b);
      if (j >= obj[i].a)
        dp[i][j] = min(dp[i][j], dp[i - 1][j - obj[i].a]);
      mn[i] = min(mn[i], dp[i][j]);
    }
  }
  for (int i = n; i >= 1; i--)
    for (int j = obj[i].b; j <= y; j++)
     dp2[i][j] = min(dp2[i + 1][j], dp2[i][j - obj[i].b] + 1);
  for (int i = 0; i <= n; i++) {
    int cst = y - mn[i];
    if (cst > 0)
      ans = max(ans, i + dp2[i + 1][cst]);
  }
  return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 24044 KB 1st lines differ - on the 1st token, expected: '689', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 89396 KB Output is correct
2 Correct 110 ms 120044 KB Output is correct
3 Correct 125 ms 118872 KB Output is correct
4 Correct 141 ms 149632 KB Output is correct
5 Correct 142 ms 155244 KB Output is correct
6 Correct 119 ms 134124 KB Output is correct
7 Correct 135 ms 125420 KB Output is correct
8 Correct 96 ms 97388 KB Output is correct
9 Correct 141 ms 150124 KB Output is correct
10 Correct 159 ms 152172 KB Output is correct
11 Correct 41 ms 50540 KB Output is correct
12 Correct 5 ms 8172 KB Output is correct
13 Correct 51 ms 63212 KB Output is correct
14 Correct 123 ms 85612 KB Output is correct
15 Correct 65 ms 88556 KB Output is correct
16 Correct 40 ms 51948 KB Output is correct
17 Correct 81 ms 87148 KB Output is correct
18 Correct 84 ms 88684 KB Output is correct
19 Incorrect 95 ms 90860 KB 1st lines differ - on the 1st token, expected: '1617', found: '1616'
20 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 87424 KB Output is correct
2 Correct 110 ms 116624 KB Output is correct
3 Correct 105 ms 119276 KB Output is correct
4 Correct 148 ms 153580 KB Output is correct
5 Incorrect 143 ms 149228 KB 1st lines differ - on the 1st token, expected: '1867', found: '1866'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
2 Halted 0 ms 0 KB -