Submission #340187

#	Time	Username	Problem	Language	Result	Execution time	Memory
340187		blue	Martian DNA (BOI18_dna)	C++11	100 / 100	116 ms	4588 KiB

dna

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int N, K, R;
    cin >> N >> K >> R;
    
    int D[N+1];
    for(int i = 1; i <= N; i++) cin >> D[i];
    
    vector<int> req(K, 0);
    vector<int> act(K, 0);
    int a, r, b;
    for(int i = 1; i <= R; i++)
    {
        cin >> a >> r;
        req[a] = r;
    }
    a = 1;
    int g = 0;
    int res = 2000000000;
    for(int i = 0; i < K; i++) g += req[i] == 0;
    for(b = 1; b <= N && g < K; b++) 
    {
        act[D[b]]++;
        if(req[D[b]] == act[D[b]]) g++;
    }
    b--;
    if(g == K) res = b;
    for(int a = 2; a <= N; a++)
    {
        act[D[a-1]]--;
        if(act[D[a-1]] == req[D[a-1]] - 1) g--;
        
        for(b++; b <= N && g < K; b++) 
        {
            act[D[b]]++;
            if(req[D[b]] == act[D[b]]) g++;
        }
        b--;
        if(g == K) res = min(res, b-a+1);
    }
    
    if(res == 2000000000) cout << "impossible\n";
    else cout << res << '\n';
    return 0;
}

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