oj.uz

Submission #697710

# Submission time Handle Problem Language Result Execution time Memory
697710 2023-02-10T21:47:43 Z tvladm2009 Jelly Flavours (IOI20_jelly) C++17
0 / 100
 65 ms 76988 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] = max(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 Incorrect 0 ms 340 KB 1st lines differ - on the 1st token, expected: '8', found: '5'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 21204 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 Incorrect 53 ms 76060 KB 1st lines differ - on the 1st token, expected: '62', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

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

Subtask #6
0 / 32.0

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