제출 #316382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316382		alextodoran	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	115 ms	78712 KiB

jelly

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int N_MAX = 2002;
const int XY_MAX = 10002;

struct Candy
{
    int a, b;
};

bool operator < (const Candy &c1, const Candy &c2)
{
    return make_pair(c1.a, c1.b) < make_pair(c2.a, c2.b);
}

int n;

Candy c[N_MAX];

int dp[N_MAX][XY_MAX];

vector <int> aux;

int find_maximum_unique(int x, int y, vector <int> a, vector <int> b)
{
    n = a.size();
    for(int i = 1; i <= n; i++)
        c[i] = Candy{a[i - 1], b[i - 1]};
    sort(c + 1, c + n + 1);
    int answer = 0;
    for(int i = 1; i <= n; i++)
    {
        int rem = INT_MAX;
        for(int j = 0; j <= x; j++)
        {
            dp[i][j] = dp[i - 1][j] + c[i].b;
            if(c[i].a <= j)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - c[i].a]);
            rem = min(rem, dp[i][j]);
        }
        rem = y - rem;
        if(rem < 0)
            break;
        aux.clear();
        for(int j = i + 1; j <= n; j++)
            aux.push_back(c[j].b);
        sort(aux.begin(), aux.end());
        int cnt = i;
        for(int val : aux)
            if(val <= rem)
            {
                rem -= val;
                cnt++;
            }
        answer = max(answer, cnt);
    }
    return answer;
}

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