Submission #311468

#	Time	Username	Problem	Language	Result	Execution time	Memory
311468		OttoTheDino	Martian DNA (BOI18_dna)	C++17	100 / 100	41 ms	4624 KiB

dna

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

#define rep(n)      for (int i = 0; i < n; ++i)
#define rep2(n)     for (int j = 0; j < n; ++j)
#define mp          make_pair
#define pb          push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;

int main() {    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, k, r;
    cin >> n >> k >> r;
    int d[n], cnt[k] = {}, mst[k] = {}, b, q, cur = 0, start = 0, ans = INT_MAX;
    rep (n) cin >> d[i];
    rep (r) {
        cin >> b >> q;
        mst[b] = q;
    }
    rep (n) {
        cnt[d[i]]++;
        if (cnt[d[i]]==mst[d[i]]) cur++;
        while (cur==r) {
            ans = min(ans, i-start+1);
            if (cnt[d[start]]==mst[d[start]]) cur--;
            cnt[d[start++]]--;
        }
    }
    
    if (ans!=INT_MAX) cout << ans << "\n";
    else cout << "impossible\n";
    
    return 0;
}

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