Submission #828570

#	Time	Username	Problem	Language	Result	Execution time	Memory
828570		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	77 ms	4512 KiB

dna

#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
const int nmax = 200002;
int N,K,R;
int arr[nmax];
int syar[nmax];
int hit[nmax]={0};
int main() {
    cin >> N >> K >> R;
    for(int i=1; i<=N; i++) {
        cin >> arr[i];
        hit[arr[i]]++;
    }
    bool impo=false;
    int inp, freq;
    for(int i=1; i<=R; i++) {
        cin >> inp >> freq;
        syar[inp] = freq;
        if(hit[inp]<freq) impo=true;
    }
    if(impo) {
        cout << "impossible" << endl;
        return 0;
    }
    memset(hit,0,sizeof(hit));
    int res=INT_MAX;
    int idx = 0;
    int uj1 = 1;
    int terms = R;
    while (idx<=N) {
        if(terms >= 1) {
            idx++;
            hit[arr[idx]]++;
            if(hit[arr[idx]]==syar[arr[idx]]) terms--;
        } else {
            res = min(res, idx-uj1+1);
            if(hit[arr[uj1]]==syar[arr[uj1]]) terms=1;
            hit[arr[uj1]]--;
            uj1++;
        }
    }
    cout << res << endl;
    return 0;
}

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