제출 #1290920

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

dna

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<algorithm>
#include<bitset>
#include<queue>
#include<numeric>
#include<climits>
#include<cstring>
#include<cmath>
using namespace std;
#define int long long
int n,k,R;
void solve() {
    cin>>n>>k>>R;
    int a[n];
    int cnt[k];
    int mn[k];
    memset(cnt, 0, sizeof(cnt));
    memset(mn,0,sizeof(mn));
    for(int i=0;i<n;i++) {
        cin>>a[i];
    }
    for(int i=0;i<R;i++) {
        int b,c;
        cin>>b>>c;
        mn[b]=c;
    }
    int l=0,r=0,z=0;
    int mn1=n+1;
    while(r<n) {
       if(z!=R) {
           cnt[a[r]]++;
           if(cnt[a[r]]==mn[a[r]]) {
               z++;
           }
           r++;
       }
        if(z==R) {
            mn1=min(mn1,r-l);
        }
        if(z==R) {
            if(cnt[a[l]]==mn[a[l]]) {
                z--;
            }
            cnt[a[l]]--;
            l++;
        }
        if(z==R) {
            mn1=min(mn1,r-l);
        }
    }
    while(z==R&&cnt[a[l]]>mn[a[l]]) {
        cnt[a[l]]--;
        l++;
    }
    if(z==R)mn1=min(mn1,r-l);
    if(mn1==n+1) {
        cout<<"impossible\n";
        return;
    }
    cout<<mn1<<'\n';
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
}

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