Submission #1167952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167952		j_vdd16	Martian DNA (BOI18_dna)	C++20	100 / 100	57 ms	2628 KiB

dna

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <chrono>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

int main() {
    int n, k, r;
    cin >> n >> k >> r;

    vi dna(n);
    loop(i, n)
        cin >> dna[i];

    vi requirements(k);
    loop(i, r) {
        int b, q;
        cin >> b >> q;

        requirements[b] = q;
    }

    int best = INT_MAX;
    int rPtr = 0;
    int reqSat = 0;
    vi freq(k);
    loop(i, n) {
        while (rPtr < n && reqSat < r) {
            int base = dna[rPtr];
            freq[base]++;
            if (requirements[base] == freq[base])
                reqSat++;
                rPtr++;
        }

        if (reqSat == r)
            best = min(best, rPtr - i);

        int base = dna[i];
        if (requirements[base] == freq[base])
            reqSat--;

        freq[base]--;
    }

    if (best == INT_MAX)
        cout << "impossible" << endl;
    else
        cout << best << endl;

    return 0;
}

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