제출 #1169306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169306		jerzyk	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	59 ms	616 KiB

jelly

#include <bits/stdc++.h>
#include "jelly.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 2007;
const int K = 10'007;
pair<int, int> tab[N];
int dp[K], il[K];
int ndp[K], nil[K];

int find_maximum_unique(int _x, int _y, vector<int> _a, vector<int> _b)
{
    int n = _a.size(), x = _x, y = _y;
    for(int i = 1; i <= n; ++i)
        tab[i] = make_pair(_a[i - 1], _b[i - 1]);
    sort(tab + 1, tab + 1 + n);
    for(int i = 1; i <= n; ++i)
    {
        //cout << "DP: " << i << " " << tab[i].st << " " << tab[i].nd << "\n";
        for(int j = 0; j <= y; ++j)
        {
            ndp[j] = dp[j]; nil[j] = il[j];
            if(nil[j] + tab[i].st <= x)
                {++ndp[j]; nil[j] += tab[i].st;}
            if(j >= tab[i].nd)
            {
                int a = dp[j - tab[i].nd] + 1, b = il[j - tab[i].nd];
                if(a > ndp[j] || (a == ndp[j] && b < nil[j]))
                    {ndp[j] = a; nil[j] = b;}
            }
            //cout << j << ": " << ndp[j] << " " << nil[j] << "\n";
        }
        for(int j = 0; j <= y; ++j)
            {dp[j] = ndp[j]; il[j] = nil[j];}
    }
    return dp[y];
}

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