| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 476401 | starplat | Jelly Flavours (IOI20_jelly) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
pair<int,int> v[2005],dp[100005];
pair<int,int> cmp(pair<int,int> a,pair<int,int> b)
{
if (a.f==-1) return b;
if (a.f<b.f) return b;
if (a.f==b.f&&a.s>b.s) return b;
return a;
}
int find_maximum_unique(int x,int y,vector<int>a, vector<int>b)
{
int n=a.size();
int ans=0;
pair<int,int> v[2005],dp[100005];
for (int i=1;i<=n;i++){
v[i]={b[i-1],a[i-1]};
}
for (int i=1;i<=x;i++) dp[i]={-1,-1};
dp[1]={0,0};
sort(v+1,v+1+n);
for (int i=1;i<=n;i++) swap(v[i].f,v[i].s);
for (int i=1;i<=n;i++){
for (int j=x;j>=0;j--){
if (dp[j].f==-1) continue;
if (j+v[i].f<=x){
dp[j+v[i].f]=cmp(dp[j+v[i].f],{dp[j].f+1,dp[j].s});
}
if (dp[j].s+v[i].s<=y){
dp[j]=cmp(dp[j],{dp[j].f+1,dp[j].s+v[i].s});
}
}
}
for (int i=0;i<=x;i++){
if (dp[i].f!=-1&&dp[i].s<=x) ans=max(dp[i].f,ans);
}
return ans;
}