Submission #1301488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301488		oa0605	Martian DNA (BOI18_dna)	C++20	100 / 100	75 ms	2732 KiB

dna

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,k,r;
    cin>>n>>k>>r;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    vector<int> f(k,0);
    for(int i=0;i<r;i++)
    {
        int b,q;
        cin>>b>>q;
        f[b]=q;
    }
    vector<int> cnt(k,0);
    int i=0,s=0,res=n+1;
    for(int j=0;j<n;j++)
    {
        cnt[v[j]]++;
        if(f[v[j]]>0&&cnt[v[j]]==f[v[j]])
            s++;
        while(s==r)
        {
            res=min(res,j-i+1);
            cnt[v[i]]--;
            if(f[v[i]]>0&&cnt[v[i]]<f[v[i]])
                s--;
            i++;
        }
    }
    if(res>n)
        cout<<"impossible";
    else
        cout<<res;
    return 0;
}

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