| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 755143 | Rafi22 | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "insects.h"
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
int ans=1,m;
int DP[2007];
int co[2007];
/*
int a[107];
map<int,int>ile;
set<int>W;
void move_inside(int i)
{
W.insert(i);
}
void move_outside(int i)
{
W.erase(i);
}
int press_button()
{
ile.clear();
int ans=0;
for(auto x:W) ans=max(ans,++ile[a[x]]);
return ans;
}
*/
void rek(vector<int>a)
{
if(sz(a)<m) return ;
int k=co[sz(a)];
vector<int>T,N;
bool is=0;
for(auto x:a)
{
move_inside(x);
if(press_button()>ans+k)
{
move_outside(x);
N.pb(x);
}
else T.pb(x);
}
if(sz(T)==m*k)
{
ans+=k;
rek(N);
}
else
{
for(auto x:T) move_outside(x);
rek(T);
}
}
int min_cardinality(int n)
{
vector<int>V,X;
for(int i=0;i<n;i++)
{
move_inside(i);
if(press_button()>1)
{
move_outside(i);
V.pb(i);
}
else
{
X.pb(i);
m++;
}
}
for(int i=m;i<=n;i++)
{
DP[i]=inf;
for(int k=1;k*m<=i;k++)
{
if(max(DP[i-m*k],DP[m*k-1])+i<DP[i])
{
co[i]=k;
DP[i]=max(DP[i-m*k],DP[m*k-1])+i;
}
}
}
rek(V);
return ans;
}
/*
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cout<<min_cardinality(n)<<endl;
return 0;
}
/*
6
5 8 9 5 9 9
*/