제출 #1169143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169143		patgra	Jelly Flavours (IOI20_jelly)	C++20	68 / 100	377 ms	197940 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();
    if(y == 0) { // p3
        vector<int> newA;
        int ans = 0;
        rep(i, 0, n) {
            if(b[i] == 0) ans++;
            else newA.pb(a[i]);
        }
        sort(newA.begin(), newA.end());
        int a2 = 0;
        while(a2 < newA.size() && x >= newA[a2]) x -= newA[a2++];
        return ans + a2;
    }
    bool podz4 = true;
    rep(i, 1, n) if(b[i] != b[i - 1]) { podz4 = false; break; }
    if(podz4) { // p4
        sort(a.begin(), a.end());
        int ans = 0;
        while(ans < n && x >= a[ans]) x -= a[ans++];
        while(ans < n && y >= b[0]) y -= b[0], ans++;
        return ans;
    }
    if(x <= 500 && y <= 500 && n <= 200) { // p1, p2
        int dp[201][501][501]; // i items, j remaining of x, k remaining of y
        repIn(i, dp) repIn(ii, i) repIn(iii, ii) iii = -1;
        dp[0][x][y] = 0;
        rep(i, 0, n) rep(j, 0, x + 1) rep(k, 0, y + 1) if(dp[i][j][k] != -1) {
            dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
            if(j >= a[i]) dp[i + 1][j - a[i]][k] = max(dp[i + 1][j - a[i]][k], dp[i][j][k] + 1);
            if(k >= b[i]) dp[i + 1][j][k - b[i]] = max(dp[i + 1][j][k - b[i]], dp[i][j][k] + 1);
        }
        int ans = 0;
        repIn(i, dp) repIn(ii, i) repIn(iii, ii) ans = max(ans, iii);
        return ans;
    }
    bool podz5 = true;
    rep(i, 0, n) if(a[i] != b[i]) { podz5 = false; break; }
    if(podz5) { // p5
        sort(a.begin(), a.end());
        int xx = x, yy = y;
        int ii = 0;
        while(ii < n && a[ii] <= xx) xx -= a[ii++];
        while(ii < n && a[ii] <= yy) yy -= a[ii++];
        if(ii == n) return ii;
        if(xx + yy < a[ii]) return ii;
        int maxExcess = xx + yy - a[ii];
        int dp[x + 1];
        repIn(i, dp) i = -1;
        dp[0] = 0;
        rep(i, 0, ii + 1) repD(j, x + 1, -1) {
            if(j + a[i] > x || dp[j] == -1) continue;
            dp[j + a[i]] = max(dp[j + a[i]], dp[j] + 1);
        }
        rep(i, x - maxExcess, x + 1) if(dp[i] != -1) return ii + 1;
        return ii;
    }
    return 0;
    // p6
}

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