Submission #1310438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310438		Samakahhh	Martian DNA (BOI18_dna)	C++20	68 / 100	2095 ms	14512 KiB

dna

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll ;
vector<ll>primes;
map<ll,ll>req,fa;
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
    ll n,k,qq;
    cin >>n>>k>>qq;
    ll a[n];
    for(ll i=0;i<n;i++){
        cin >>a[i];
    }
    while(qq--){
    ll x,y;
    cin >>x>>y;
    req[x]=y;
    }

    ll l=0,r=0,mn=1e9;

    while(r<n||l<n){
        //check
        bool is=1;
        for(auto p : req){
        if(fa[p.first]<p.second){
            is=0;
        }
        }

        if(is==0&&r<n){
        fa[a[r]]++;
            r++;

        }
        else{
             if(is==1){   
                mn=min(mn,r-l);
             }
            fa[a[l]]--;
            l++;
        }
    }
    if(mn!=1e9)
    cout <<mn<<endl;

    else{
        cout <<"impossible"<<endl;
    }
    return 0;
}

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