Submission #1290932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290932		ayathk	Martian DNA (BOI18_dna)	C++20	40 / 100	625 ms	1114112 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define fi first 
#define se second 
#define int long long 
#define all(a) a.begin(),a.end()
#define pb push_back
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const int lg = 30 ;

void solve(){
    int n,k,q;
    cin>>n>>k>>q;

    vector <int> a(n);
    for(int& i : a)cin>>i;

    vector <int> nm(maxn, 0);
    while(q--){
        int b,c;
        cin>>b>>c;
        nm[b] = c;
    }

    vector <vector <int>> pre(k, vector <int> (n));
    for(int i = 0;i < k;i++){
        int sm = 0;
        for(int j = 0;j < n;j++){
            if(a[j] == i)sm++;
            pre[i][j] = sm;
        }
    }

    int mn = 1e9,st = -1,en = 0;
    while(en < n){
        bool ps = true;

        for(int j = 0;j < k;j++){
            if(st == -1){
                if(pre[j][en] < nm[j]){
                    ps = 0;

                }
            }
            else{
                if(pre[j][en] - pre[j][st] < nm[j]){
                    ps = 0;
                }
            }   
        }
        if(ps){
            mn = min(mn, en - st);
            st++;
        }
        else{
            en++;
        }
    }

    if(st == -1){
        cout<<"impossible";
    }
    else{
        cout<<mn;
    }
    cout<<'\n';
}
signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int qu;
    qu = 1;
    
    while(qu--){
        solve();
    }
    return 0;
}

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