oj.uz

Submission #321856

# Submission time Handle Problem Language Result Execution time Memory
321856 2020-11-13T12:55:55 Z Pety Jelly Flavours (IOI20_jelly) C++14
0 / 100
 166 ms 156268 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 = 0; i <= n; i++)
    for (int j = 0; j <= x; j++)
      dp[i][j] = 2e9;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
     mn[i] = 2e9;
    for (int j = 0; j <= x;j++) {
      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 = 0; j <= y; j++)
     dp2[i][j] = min(dp2[i + 1][j], (j >= obj[i].b ? dp2[i][j - obj[i].b] + 1 : (int)2e9));
  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 492 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 492 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 25 ms 29292 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 98 ms 94572 KB Output is correct
2 Correct 152 ms 155756 KB Output is correct
3 Correct 148 ms 156268 KB Output is correct
4 Correct 154 ms 149740 KB Output is correct
5 Correct 160 ms 155244 KB Output is correct
6 Correct 154 ms 149652 KB Output is correct
7 Correct 160 ms 154348 KB Output is correct
8 Correct 145 ms 150252 KB Output is correct
9 Correct 152 ms 150124 KB Output is correct
10 Correct 166 ms 152288 KB Output is correct
11 Correct 76 ms 88940 KB Output is correct
12 Correct 9 ms 15852 KB Output is correct
13 Correct 76 ms 86764 KB Output is correct
14 Correct 123 ms 85612 KB Output is correct
15 Correct 77 ms 88556 KB Output is correct
16 Correct 76 ms 84204 KB Output is correct
17 Correct 89 ms 87404 KB Output is correct
18 Correct 97 ms 94444 KB Output is correct
19 Incorrect 101 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 100 ms 93568 KB Output is correct
2 Correct 157 ms 150124 KB Output is correct
3 Correct 147 ms 154348 KB Output is correct
4 Correct 157 ms 153580 KB Output is correct
5 Incorrect 156 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 492 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
2 Halted 0 ms 0 KB -