Submission #548156

#	Time	Username	Problem	Language	Result	Execution time	Memory
548156		QuantumK9	Martian DNA (BOI18_dna)	C++17	100 / 100	233 ms	13596 KiB

dna

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple 

using namespace std;

void solve(){

    int n,k,r; cin >> n >> k >> r;

    int count[k]; memset( count, 0, sizeof count ); 
    bool needs[k]; memset( needs, false, sizeof needs );

    int a[n]; for( int i = 0; i < n; i++ ){ cin >> a[i]; count[ a[i] ]++; }

    map<int,int> required;

    set<int> unsatisfied;
    
    for( int i = 0; i < r; i++ ){
        int b,k; cin >> b >> k;
        required[b] = k;
        needs[b] = true;
        unsatisfied.insert(b);
    }

    for( auto i : required ){
        if( count[ i.first ] < i.second ){ cout << "impossible" << endl; return; }
    }

    // reset count
    memset( count, 0, sizeof count );

    // fill
    int ind = 0;
    while( !unsatisfied.empty() ){

        count[ a[ind] ]++; // add him to list
        if( needs[ a[ind] ] ){
            if( unsatisfied.find( a[ind] ) != unsatisfied.end() && count[ a[ind] ] >= required[ a[ind] ] ){ unsatisfied.erase( a[ind] ); }
        }
        ind++;
    }

    //cout << ind << endl;

    int ans = ind;
    bool flag = false;

    for( int rS = 0; rS < n-1; rS++ ){

        count[ a[rS] ]--;
        if( needs[ a[rS] ] ){
            if( count[ a[rS] ] < required[ a[rS] ] ){ unsatisfied.insert( a[rS] ); }
        }

        while( !unsatisfied.empty() ){

            if( ind == n ){ flag = true; break; }

            count[ a[ind] ]++; // add him to list
            if( needs[ a[ind] ] ){
                if( unsatisfied.find( a[ind] ) != unsatisfied.end() && count[ a[ind] ] >= required[ a[ind] ] ){ unsatisfied.erase( a[ind] ); }
            }
            ind++;

        }

        if( flag ){ break; }

        ans = min( ans, ind-rS-1 );
    }

    cout << ans << endl;

    return;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) { solve(); }

    return 0;
}

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