Submission #993889

#	Time	Username	Problem	Language	Result	Execution time	Memory
993889		AndrijaM	Martian DNA (BOI18_dna)	C++14	100 / 100	26 ms	8620 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=2e5+10;
const int mod=1e9+7;

int m[maxn];
int cnt[maxn];
int K[maxn];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(m,-1,sizeof m);
    ///freopen("prieteni.in","r",stdin);
    ///freopen("prieteni.out","w",stdout);
    int n,k,r;
    cin>>n>>k>>r;
    int x[n];
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        K[x[i]]++;
    }
    bool T=true;
    for(int i=0;i<r;i++)
    {
        int koj,kol;
        cin>>koj>>kol;
        m[koj]=kol;
        if(K[koj]<m[koj])
        {
            T=false;
        }
    }
    if(!T)
    {
        cout<<"impossible"<<endl;
        return 0;
    }
    int ok=0;
    int ans=n;
    int j=-1;
    for(int i=0;i<n;i++)
    {
        cnt[x[i]]++;
        if(cnt[x[i]]==m[x[i]])
        {
            ok++;
        }
        if(ok==r)
        {
            while(j+1<i && cnt[x[j+1]]!=m[x[j+1]])
            {
                cnt[x[j+1]]--;
                j++;
            }
            ans=min(ans, i-(j+1)+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32