oj.uz

Submission #697711

# Submission time Handle Problem Language Result Execution time Memory
697711 2023-02-10T21:48:18 Z tvladm2009 Jelly Flavours (IOI20_jelly) C++17
10 / 100
 94 ms 78616 KB 
#include <bits/stdc++.h>
#include "jelly.h"

using namespace std;

typedef long long ll;

const int N_MAX = 2000;
const int X_MAX = 10000;
const int INF = 1e9;

struct Jelly {
    int a;
    int b;
};

Jelly c[N_MAX + 2];

int dp[N_MAX + 2][X_MAX + 2];

bool operator < (const Jelly &a, const Jelly &b) {
    return make_pair(a.a, a.b) < make_pair(b.a, b.b);
}

int find_maximum_unique (int x, int y, vector <int> a, vector <int> b) {
    int n = a.size();
    for (int i = 1; i <= n; i++) {
        c[i] = Jelly{a[i - 1], b[i - 1]};
    }
    sort(c + 1, c + n + 1);
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        int rem = INF;
        for (int j = 0; j <= x; j++) {
            dp[i][j] = dp[i - 1][j] + c[i].b;
            if (j >= c[i].a) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - c[i].a]);
            }
            rem = min(rem, dp[i][j]);
        }
        rem = y - rem;
        if (rem < 0) {
            continue;
        }
        vector <int> aux;
        for (int j = i + 1; j <= n; j++) {
            aux.push_back(c[i].b);
        }
        sort(aux.begin(), aux.end());
        int cnt = i;
        for (int it : aux) {
            if (it <= rem) {
                rem -= it;
                cnt++;
            }
        }
        answer = max(answer, cnt);
    }
    return answer;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 320 KB 1st lines differ - on the 1st token, expected: '7', found: '10'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 320 KB 1st lines differ - on the 1st token, expected: '7', found: '10'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 76068 KB Output is correct
2 Correct 58 ms 77920 KB Output is correct
3 Correct 58 ms 78236 KB Output is correct
4 Correct 85 ms 74916 KB Output is correct
5 Correct 81 ms 77756 KB Output is correct
6 Correct 56 ms 74784 KB Output is correct
7 Correct 57 ms 77188 KB Output is correct
8 Correct 55 ms 75224 KB Output is correct
9 Correct 77 ms 75104 KB Output is correct
10 Correct 79 ms 76228 KB Output is correct
11 Correct 8 ms 12380 KB Output is correct
12 Correct 4 ms 8020 KB Output is correct
13 Correct 9 ms 9668 KB Output is correct
14 Correct 25 ms 9608 KB Output is correct
15 Correct 22 ms 12108 KB Output is correct
16 Correct 5 ms 8772 KB Output is correct
17 Correct 56 ms 78584 KB Output is correct
18 Correct 57 ms 74708 KB Output is correct
19 Correct 80 ms 76592 KB Output is correct
20 Correct 76 ms 77068 KB Output is correct
21 Correct 58 ms 76104 KB Output is correct
22 Correct 56 ms 77896 KB Output is correct
23 Correct 58 ms 78236 KB Output is correct
24 Correct 82 ms 74952 KB Output is correct
25 Correct 80 ms 77644 KB Output is correct
26 Correct 56 ms 74812 KB Output is correct
27 Correct 57 ms 77260 KB Output is correct
28 Correct 57 ms 75256 KB Output is correct
29 Correct 79 ms 75212 KB Output is correct
30 Correct 82 ms 76188 KB Output is correct
31 Correct 8 ms 12372 KB Output is correct
32 Correct 3 ms 8020 KB Output is correct
33 Correct 5 ms 9556 KB Output is correct
34 Correct 24 ms 9668 KB Output is correct
35 Correct 23 ms 12164 KB Output is correct
36 Correct 5 ms 8788 KB Output is correct
37 Correct 55 ms 78528 KB Output is correct
38 Correct 54 ms 74736 KB Output is correct
39 Correct 79 ms 76620 KB Output is correct
40 Correct 79 ms 77008 KB Output is correct
41 Correct 54 ms 76064 KB Output is correct
42 Correct 63 ms 77908 KB Output is correct
43 Correct 57 ms 78196 KB Output is correct
44 Correct 79 ms 74976 KB Output is correct
45 Correct 81 ms 77708 KB Output is correct
46 Correct 56 ms 74832 KB Output is correct
47 Correct 55 ms 77284 KB Output is correct
48 Correct 59 ms 75304 KB Output is correct
49 Correct 78 ms 75212 KB Output is correct
50 Correct 77 ms 76148 KB Output is correct
51 Correct 8 ms 12360 KB Output is correct
52 Correct 3 ms 8020 KB Output is correct
53 Correct 6 ms 9556 KB Output is correct
54 Correct 23 ms 9648 KB Output is correct
55 Correct 23 ms 12192 KB Output is correct
56 Correct 7 ms 8776 KB Output is correct
57 Correct 56 ms 78604 KB Output is correct
58 Correct 54 ms 74724 KB Output is correct
59 Correct 79 ms 76532 KB Output is correct
60 Correct 80 ms 77120 KB Output is correct
61 Correct 57 ms 76136 KB Output is correct
62 Correct 58 ms 77956 KB Output is correct
63 Correct 58 ms 78304 KB Output is correct
64 Correct 77 ms 74880 KB Output is correct
65 Correct 81 ms 77704 KB Output is correct
66 Correct 55 ms 74808 KB Output is correct
67 Correct 56 ms 77260 KB Output is correct
68 Correct 69 ms 75152 KB Output is correct
69 Correct 79 ms 75140 KB Output is correct
70 Correct 77 ms 76236 KB Output is correct
71 Correct 8 ms 12380 KB Output is correct
72 Correct 4 ms 7996 KB Output is correct
73 Correct 6 ms 9676 KB Output is correct
74 Correct 23 ms 9580 KB Output is correct
75 Correct 23 ms 12148 KB Output is correct
76 Correct 6 ms 8788 KB Output is correct
77 Correct 57 ms 78616 KB Output is correct
78 Correct 55 ms 74740 KB Output is correct
79 Correct 79 ms 76612 KB Output is correct
80 Correct 79 ms 77096 KB Output is correct
81 Correct 55 ms 76072 KB Output is correct
82 Correct 60 ms 78024 KB Output is correct
83 Correct 58 ms 78284 KB Output is correct
84 Correct 82 ms 74988 KB Output is correct
85 Correct 94 ms 77636 KB Output is correct
86 Correct 54 ms 74820 KB Output is correct
87 Correct 55 ms 77260 KB Output is correct
88 Correct 59 ms 75248 KB Output is correct
89 Correct 93 ms 75124 KB Output is correct
90 Correct 86 ms 76256 KB Output is correct
91 Correct 8 ms 12372 KB Output is correct
92 Correct 3 ms 8020 KB Output is correct
93 Correct 6 ms 9672 KB Output is correct
94 Correct 22 ms 9596 KB Output is correct
95 Correct 23 ms 12200 KB Output is correct
96 Correct 5 ms 8788 KB Output is correct
97 Correct 56 ms 78540 KB Output is correct
98 Correct 54 ms 74792 KB Output is correct
99 Correct 79 ms 76620 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 76952 KB 1st lines differ - on the 1st token, expected: '154', found: '541'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 320 KB 1st lines differ - on the 1st token, expected: '7', found: '10'
3 Halted 0 ms 0 KB -