Submission #1022021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022021		vjudge1	Martian DNA (BOI18_dna)	C++98	0 / 100	54 ms	4908 KiB

dna

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 200005;

void solve() {
    int n, k, R;
    cin >> n >> k >> R;
    vector<int>req(k, 0);
    int a[n];
    for(int i=0; i<n; ++i) cin >> a[i];
    for(int i=0; i<R; ++i) {
        int b, q;
        cin >> b >> q;
        req[b] = q;
    }
    int need = R, l = 0, r = 0, ans = n+1;
    vector<int>cnt(k, 0);
    ++cnt[a[0]];
    if(req[a[0]] == 1) --need;
    while(r < n) {
        while(r != l) {
            if((cnt[a[l]]-1) >= req[a[l]]) {
                ++l;
                --cnt[a[l]];
            } else break;
        }
        if(!need) ans = min(ans, r-l+1);
        if(r == n-1) break;
        ++r, ++cnt[a[r]];
        if(cnt[a[r]] == req[a[r]]) --need;
    }
    if(ans == n+1) cout << "impossible" << endl;
    else cout << ans << endl;
}

signed main() {
    int t = 1;
    while(t--) solve();

    return 0;
}

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