제출 #1312059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312059		norrawichzzz	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	129 ms	154876 KiB

jelly

#include <bits/stdc++.h>
using namespace std;


int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
    int n=a.size();

    vector<pair<int,int>> od(n);
    for (int i=0; i<n; i++) od[i] = {a[i], b[i]};

    sort(od.begin(), od.end());

    vector<vector<pair<int,int>>> dp(n+1, vector<pair<int,int>>(y+1));
    dp[0][0] = {0, 0};

    for (int i=1; i<=n; i++) {
        for (int j=y; j>=0; j--) {
            dp[i][j] = dp[i-1][j];

            int addx = od[i-1].first, addy=od[i-1].second;

            if (dp[i-1][j].first + addx <= x) {
                dp[i][j].first += addx;
                dp[i][j].second++;
            }
            
            if (j - addy >= 0) {
                if (dp[i-1][j-addy].second + 1 > dp[i][j].second) dp[i][j] = {dp[i-1][j-addy].first, dp[i-1][j-addy].second+1};
                else if (dp[i-1][j-addy].second + 1 == dp[i][j].second) dp[i][j].first = min(dp[i][j].first, dp[i-1][j-addy].first);
            }
        }
    } 
    return dp[n][y].second;
}
/*
int main() {
    int n,x,y;
    cin>> n>> x>> y;

    vector<int> a(n), b(n);
    for (int i=0; i<n; i++) cin>> a[i];
    for (int i=0; i<n; i++) cin>> b[i];  

    cout<< find_maximum_unique(x, y, a, b);
}*/

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