제출 #1170506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170506		patgra	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	173 ms	77640 KiB

jelly

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

#include "jelly.h"
#include <vector>

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	int n = (int)a.size();
    vector<pair<int, int>> xd;
    rep(i, 0, n) xd.pb({a[i], b[i]});
    ranges::sort(xd);
    a.clear();
    b.clear();
    repIn2(aa, bb, xd) a.pb(aa), b.pb(bb);
    vector<vector<int>> dp(n + 1, vector<int>(x + 1, 1e9));
    vector<int> minY(n + 1, 1e9);
    dp[0][0] = 0;
    rep(i, 0, n) rep(j, 0, x + 1) {
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + b[i]);
        if(j + a[i] <= x) dp[i + 1][j + a[i]] = min(dp[i + 1][j + a[i]], dp[i][j]);
        minY[i] = min(minY[i], dp[i][j]);
    }
    if(minY[n] <= y) return n;
    int ans = 0;
    priority_queue<int, vector<int>, greater<>> Q;
    repD(i, n - 1, -1) {
        if(minY[i] > y) continue;
        rep(j, i, n) Q.push(b[j]);
        auto rem = y - minY[i];
        while(!Q.empty() && rem >= Q.top()) rem -= Q.top(), Q.pop();
        ans = max(ans, (int)(n - Q.size()));
        while(!Q.empty()) Q.pop();
    }
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 14 / 14
• Subtask 6: 32 / 32