Submission #755144

#	Time	Username	Problem	Language	Result	Execution time	Memory
755144		Rafi22	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	69 ms	456 KiB

insects

#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
*/

Compilation message (stderr)

insects.cpp:111:1: warning: "/*" within comment [-Wcomment]
  111 | /*
      |  
insects.cpp: In function 'void rek(std::vector<int>)':
insects.cpp:47:10: warning: unused variable 'is' [-Wunused-variable]
   47 |     bool is=0;
      |          ^~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 74.89 / 75