제출 #1280272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280272		Newtonabc	Martian DNA (BOI18_dna)	C++20	100 / 100	24 ms	3256 KiB

dna

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int ck[N],r=0,req[N],cnt[N],arr[N];
//O(n log n) able but solved in O(n) :>
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k,r;
    cin>>n >>k >>r;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=0;i<r;i++){
        int a,b;
        cin>>a >>b;
        req[a]=b;
    }
    for(int i=1;i<=n;i++){
        ck[arr[i]]++;
        if(ck[arr[i]]-1<req[arr[i]] && ck[arr[i]]>=req[arr[i]]) r=i;
    }
    for(int i=0;i<k;i++){
        if(ck[i]<req[i]){
            cout<<"impossible";
            return 0;
        }
    }
    int ans=r;
    for(int i=1;i<=r;i++) cnt[arr[i]]++;
    for(int i=2;i<=n;i++){
        cnt[arr[i-1]]--;
        while(cnt[arr[i-1]]<req[arr[i-1]] && r+1<n) r++,cnt[arr[r]]++;
        if(cnt[arr[i-1]]<req[arr[i-1]]) break;
        ans=min(ans,r-i+1);
    }
    cout<<ans;
}

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