Submission #646627

#	Time	Username	Problem	Language	Result	Execution time	Memory
646627		alextodoran	Martian DNA (BOI18_dna)	C++17	100 / 100	31 ms	4468 KiB

dna

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N, K, R;
int D[N_MAX + 2];
int Q[N_MAX + 2];

int cnt[N_MAX + 2];
int ok;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K >> R;
    for (int i = 1; i <= N; i++) {
        cin >> D[i];
    }
    for (int i = 1; i <= R; i++) {
        int B;
        cin >> B;
        cin >> Q[B];
    }
    ok = K - R;
    int r = 0;
    while (r <= N && ok < K) {
        r++;
        if (cnt[D[r]] + 1 == Q[D[r]]) {
            ok++;
        }
        cnt[D[r]]++;
    }
    if (r == N + 1) {
        cout << "impossible\n";
        return 0;
    }
    int answer = INT_MAX;
    int l = 1;
    while (r <= N) {
        while (l < r && cnt[D[l]] - 1 >= Q[D[l]]) {
            cnt[D[l]]--;
            l++;
        }
        answer = min(answer, r - l + 1);
        cnt[D[++r]]++;
    }
    cout << answer << "\n";

    return 0;
}

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