Submission #951602

#	Time	Username	Problem	Language	Result	Execution time	Memory
951602		SaMuEl0516	Martian DNA (BOI18_dna)	C++17	100 / 100	25 ms	4856 KiB

dna

#include<bits/stdc++.h>
using namespace std;
int q[(int)2e5+5],cnt[(int)2e5+5],a[(int)2e5+5];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,k,r,x,y,ans=1e9;
    cin>>n>>k>>r;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<r;i++){
        cin>>x>>y;
        q[x]=y;
    }
    for(int i=0,j=0;;j++){
        if(j==n)break;
        if(++cnt[a[j]]==q[a[j]])r--;
        if(r==0){
            while(cnt[a[i]]-1>=q[a[i]]){
                cnt[a[i]]--;
                i++;
            }
            ans=min(ans,j-i+1);
        }
    }
    if(ans==1e9)cout<<"impossible";
    else cout<<ans;
}

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