oj.uz

Submission #697713

# Submission time Handle Problem Language Result Execution time Memory
697713 2023-02-10T21:54:38 Z tvladm2009 Jelly Flavours (IOI20_jelly) C++17
10 / 100
 84 ms 78596 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;

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 = INT_MAX;
        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 0 ms 340 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 0 ms 340 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 14 ms 21184 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 54 ms 76072 KB Output is correct
2 Correct 57 ms 77876 KB Output is correct
3 Correct 57 ms 78184 KB Output is correct
4 Correct 82 ms 74848 KB Output is correct
5 Correct 84 ms 77652 KB Output is correct
6 Correct 53 ms 74828 KB Output is correct
7 Correct 53 ms 77236 KB Output is correct
8 Correct 56 ms 75240 KB Output is correct
9 Correct 78 ms 75256 KB Output is correct
10 Correct 78 ms 76216 KB Output is correct
11 Correct 8 ms 12372 KB Output is correct
12 Correct 4 ms 8020 KB Output is correct
13 Correct 6 ms 9588 KB Output is correct
14 Correct 22 ms 9684 KB Output is correct
15 Correct 22 ms 12104 KB Output is correct
16 Correct 5 ms 8788 KB Output is correct
17 Correct 56 ms 78524 KB Output is correct
18 Correct 54 ms 74736 KB Output is correct
19 Correct 84 ms 76600 KB Output is correct
20 Correct 80 ms 77044 KB Output is correct
21 Correct 56 ms 76072 KB Output is correct
22 Correct 55 ms 77940 KB Output is correct
23 Correct 55 ms 78184 KB Output is correct
24 Correct 76 ms 74956 KB Output is correct
25 Correct 81 ms 77712 KB Output is correct
26 Correct 53 ms 74812 KB Output is correct
27 Correct 54 ms 77144 KB Output is correct
28 Correct 55 ms 75212 KB Output is correct
29 Correct 76 ms 75192 KB Output is correct
30 Correct 77 ms 76212 KB Output is correct
31 Correct 8 ms 12372 KB Output is correct
32 Correct 3 ms 8020 KB Output is correct
33 Correct 6 ms 9572 KB Output is correct
34 Correct 23 ms 9620 KB Output is correct
35 Correct 22 ms 12120 KB Output is correct
36 Correct 5 ms 8788 KB Output is correct
37 Correct 56 ms 78552 KB Output is correct
38 Correct 54 ms 74744 KB Output is correct
39 Correct 79 ms 76532 KB Output is correct
40 Correct 76 ms 77048 KB Output is correct
41 Correct 56 ms 76072 KB Output is correct
42 Correct 55 ms 77900 KB Output is correct
43 Correct 57 ms 78208 KB Output is correct
44 Correct 77 ms 74856 KB Output is correct
45 Correct 81 ms 77624 KB Output is correct
46 Correct 53 ms 74832 KB Output is correct
47 Correct 59 ms 77328 KB Output is correct
48 Correct 55 ms 75128 KB Output is correct
49 Correct 77 ms 75072 KB Output is correct
50 Correct 76 ms 76144 KB Output is correct
51 Correct 8 ms 12372 KB Output is correct
52 Correct 3 ms 8020 KB Output is correct
53 Correct 6 ms 9556 KB Output is correct
54 Correct 22 ms 9636 KB Output is correct
55 Correct 23 ms 12140 KB Output is correct
56 Correct 5 ms 8788 KB Output is correct
57 Correct 58 ms 78592 KB Output is correct
58 Correct 52 ms 74776 KB Output is correct
59 Correct 79 ms 76504 KB Output is correct
60 Correct 75 ms 76992 KB Output is correct
61 Correct 53 ms 76012 KB Output is correct
62 Correct 55 ms 77884 KB Output is correct
63 Correct 59 ms 78184 KB Output is correct
64 Correct 77 ms 74904 KB Output is correct
65 Correct 82 ms 77732 KB Output is correct
66 Correct 54 ms 74788 KB Output is correct
67 Correct 54 ms 77176 KB Output is correct
68 Correct 62 ms 75192 KB Output is correct
69 Correct 77 ms 75104 KB Output is correct
70 Correct 76 ms 76132 KB Output is correct
71 Correct 8 ms 12372 KB Output is correct
72 Correct 4 ms 8020 KB Output is correct
73 Correct 6 ms 9588 KB Output is correct
74 Correct 22 ms 9636 KB Output is correct
75 Correct 23 ms 12108 KB Output is correct
76 Correct 5 ms 8788 KB Output is correct
77 Correct 55 ms 78596 KB Output is correct
78 Correct 55 ms 74700 KB Output is correct
79 Correct 82 ms 76560 KB Output is correct
80 Correct 76 ms 77092 KB Output is correct
81 Correct 55 ms 76064 KB Output is correct
82 Correct 55 ms 77932 KB Output is correct
83 Correct 58 ms 78200 KB Output is correct
84 Correct 76 ms 74956 KB Output is correct
85 Correct 84 ms 77804 KB Output is correct
86 Correct 56 ms 74848 KB Output is correct
87 Correct 54 ms 77252 KB Output is correct
88 Correct 63 ms 75200 KB Output is correct
89 Correct 76 ms 75164 KB Output is correct
90 Correct 77 ms 76200 KB Output is correct
91 Correct 9 ms 12372 KB Output is correct
92 Correct 4 ms 8020 KB Output is correct
93 Correct 6 ms 9556 KB Output is correct
94 Correct 23 ms 9680 KB Output is correct
95 Correct 23 ms 12184 KB Output is correct
96 Correct 5 ms 8788 KB Output is correct
97 Correct 56 ms 78492 KB Output is correct
98 Correct 53 ms 74704 KB Output is correct
99 Correct 78 ms 76592 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 76984 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 0 ms 340 KB 1st lines differ - on the 1st token, expected: '7', found: '10'
3 Halted 0 ms 0 KB -