Submission #467390

#	Time	Username	Problem	Language	Result	Execution time	Memory
467390		Ozy	Martian DNA (BOI18_dna)	C++17	100 / 100	42 ms	5328 KiB

dna

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 200000

lli n,r,k,a,b,ini,falt,res;
lli arr[MAX+2], requeridos[MAX+2];

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

    cin >> n >> k >> r;
    rep(i,1,n) cin >> arr[i];

    rep(i,1,r) {
        cin >> a >> b;
        requeridos[a] = b;
        falt += b;
    }

    ini = 1;
    res = -1;

    rep(fin,1,n) {

        a = arr[fin];
        if(requeridos[a] > 0) falt--;
        requeridos[a]--;

        while (falt == 0) {

            a = fin-ini+1;
            if (res == -1 || a < res) res = a;

            a = arr[ini++];
            if (requeridos[a] >= 0) falt++;
            requeridos[a]++;
        }
    }

    if (res == -1) cout << "impossible";
    else cout << res;
}

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