제출 #1169210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169210		TlenekWodoru	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	277 ms	153000 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
int find_maximum_unique(int x, int y, vector<int> a, vector<int> b)
{
    const int n=a.size();
    vector<pair<int,int>>tab(n+1);
    vector<vector<int>>dp(n+2,vector<int>(x+2));
    vector<vector<int>>dp2(n+2,vector<int>(y+2));
    for(int i=1;i<=n;i++)
    {
        tab[i]={a[i-1],b[i-1]};
    }
    sort(tab.begin()+1,tab.end());
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=x;j++)
        {
            dp[i][j]=dp[i-1][j]+tab[i].second;
            if(j>0)
            {
                dp[i][j]=min(dp[i][j],dp[i][j-1]);
            }
            if(j>=tab[i].first)
            {
                dp[i][j]=min(dp[i][j],dp[i-1][j-tab[i].first]);
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=y;j++)
        {
            dp2[i][j]=dp2[i+1][j];
            if(j>0)
            {
                dp2[i][j]=max(dp2[i][j],dp2[i][j-1]);
            }
            if(j>=tab[i].second)
            {
                dp2[i][j]=max(dp2[i][j],dp2[i+1][j-tab[i].second]+1);
            }
        }
    }
    int wyn=0;
    for(int i=0;i<=n;i++)
    {
        if(dp[i][x]>y){continue;}
        wyn=max(wyn,i+dp2[i+1][y-dp[i][x]]);
    }
	return wyn;
}

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