Submission #1310429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310429		Samakahhh	Martian DNA (BOI18_dna)	C++20	40 / 100	2095 ms	12048 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,r;
    cin >>n>>k>>r;
    ll a[n];
    for(ll i=0;i<n;i++){
        cin >>a[i];
    }
    ll mn=999999;
    while(r--){
    ll x,y;
    cin >>x>>y;
    req[x]=y;
    }

    for(ll i=0;i<n;i++){
            fa.clear();
        for(ll j=i;j<n;j++){
            fa[a[j]]++;
            bool is=1;
            for(auto p : req){
                if(fa[p.first]<p.second){
                    is=0;
                }
            }
            if(is==1){
                mn=min((j-i)+1,mn);
                //cout <<i<<' '<<j<<endl;
            }
        }


    }

    if(mn==999999){
        cout <<"impossible"<<endl;
    }
    else{
        cout <<mn<<endl;
    }


    return 0;
}

    

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