Submission #1367023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367023		lizi14	Martian DNA (BOI18_dna)	C++20	0 / 100	2094 ms	8236 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define ss second
#define ina insert
#define pb push_back
signed main(){
    int n,m,t;
    cin>>n>>m>>t;
    int x[n];
    for(int i=0; i<n; i++){
        cin>>x[i];
    }
    vector<pair<int,int>>p;
    for(int q=0; q<t; q++){
        int a,b;
        cin>>a>>b;
        p.pb({a,b});
    }
    int ans=1e18;
    int k=0;
    map<int,int>mp;
    for(int i=0; i<n; i++){
        if(i>0){
            mp[x[i-1]]--;
        }
        //mp[x[i]]++;
        int bati=0;
        while(k<n){
            int hi=0;
            for(int j=0; j<t; j++){
                if(mp[p[j].f]<p[j].ss){
                    hi=1;
                    break;
                }
            }
            if(hi==0)break;
            else {
                mp[x[k]]++;
                k++;
                
            }
            if(k==n && hi==1){
                bati=1;
            }
        }
        //cout<<k<<" ";
        if(k==n)continue;
        if(bati==1){
            continue;
        }
        ans=min(ans,k-i);
    }
    if(ans==1e18){
        cout<<"impossible"<<endl;
    }
    else cout<<ans<<endl;
}

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