Submission #1013769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013769		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	27 ms	2648 KiB

dna

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n,k,q; cin >> n >> k >> q;
    int a[n], target[k] = {}, frq[k] = {};
    for (int& i : a) {
        cin >> i;
        frq[i]++;
    }

    while (q--) {
        int x, y; cin >> x >> y;
        target[x] = y;
    }
    for (int val = 0; val < k; val++) {
        if (target[val] > frq[val]) {
            cout << "impossible";
            return 0;
        } else {
            frq[val] = 0;
        }
    }

    int cnt = count(target, target + k, 0);
    int l = 0, r = -1;
    int ans = n;
    while (++r < n) {
        if (++frq[a[r]] == target[a[r]]) cnt++;
        if (cnt == k) {
            while (cnt == k) {
                if (--frq[a[l]] < target[a[l]]) {
                    cnt--;
//                    break;
                }
                l++;
            }
            ans = min(ans, r-(l-1)+1);
//            cout << l << " " << r << " " << cnt << "\n";
//            for (int x : frq) cout << x << " ";
//            cout << "\n";
//            for (int x : target) cout << x << " " ;
//            cout << "\n\n";
        }
    }
    cout << ans;
}

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