Submission #1127254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127254		Ludissey	Martian DNA (BOI18_dna)	C++20	100 / 100	51 ms	2632 KiB

dna

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> a;
vector<int> req;
int n,K,R; 
bool f(int k){
    vector<int> has(K,0);
    int Nr=0;
    for (int i = 0; i < k; i++) has[a[i]]++;
    for (int i = 0; i < K; i++)
    {
        if(has[i]>=req[i]) Nr++;
    }
    for (int j = k; j < n; j++)
    {
        if(Nr==K) return true;
        if(req[a[j]]==has[a[j]]+1) Nr++;
        has[a[j]]++;
        if(req[a[j-k]]==has[a[j-k]]) Nr--;
        has[a[j-k]]--;
    }
    return (Nr==K);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> K >> R;
    a.resize(n);
    req.resize(K,0);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < R; i++) {
        int b,v; cin >> b >> v;
        req[b]=v;
    }
    
    int l=1; int r=n;
    int ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(f(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if(ans==-1) cout << "impossible\n";
    else cout << ans << "\n";

    return 0;
}

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