Submission #643509

#	Time	Username	Problem	Language	Result	Execution time	Memory
643509		KindaNameless	Martian DNA (BOI18_dna)	C++14	100 / 100	33 ms	3504 KiB

dna

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

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

    int N, K, R; cin >> N >> K >> R;

    vector<int> need(K), cnt(K), D(N+1);
    for(int i = 1; i <= N; ++i){
        cin >> D[i];
    }

    for(int i = 1; i <= R; ++i){
        int B, Q; cin >> B >> Q;
        need[B] = Q;
    }

    int done = 0;
    for(int i = 0; i < K; ++i){
        if(need[i] == 0)done++;
    }

    int l = 1, r, answer = 1e9;
    for(r = 1; r <= N; ++r){
        cnt[D[r]]++;
        if(cnt[D[r]] == need[D[r]])done++;
        while(l < r && cnt[D[l]] > need[D[l]]){
            cnt[D[l++]]--;
        }
        if(done == K){
            answer = min(answer, r - l + 1);
        }
    }

    if(answer > N)cout << "impossible";
    else cout << answer;

    return 0;
}

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