Submission #696480

#	Time	Username	Problem	Language	Result	Execution time	Memory
696480		josiftepe	Martian DNA (BOI18_dna)	C++14	100 / 100	40 ms	4012 KiB

dna

#include <iostream>
#include <vector>
#include <map>
using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    int n, k;
    cin>>n >> k;
    int m;
    cin>>m;

    vector<int> req(k + 1, 0);
    
    vector<int>v;
    
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        v.push_back(a);
    }
    for(int j=0; j<m; j++){
    int a, b;
    cin>>a>>b;
    req[a] = b;
    }
    
   
    int min_length=2e9;
    int tmp = m;
    int j = 0;
    for(int i = 0; i < n; i++) {
        while(tmp > 0 and j < n) {
            req[v[j]]--;
            if(req[v[j]] == 0) {
                tmp--;
            }
            j++;
        }
        
        if(tmp == 0) {
            min_length = min(min_length, j - i);
        }
        req[v[i]]++;
        
        if(req[v[i]] > 0) {
            tmp++;
        }
    }
    
  
    if(min_length == 2e9) {
        cout << "impossible";
    }
    else
    cout << min_length  << endl;
    return 0;
}
/*
 5 2 2
 0 1 1 0 1
 0 1
1 1
 
 13 4 3
 1 1 3 2 0 1 2 0 0 0 0 3 1
 0 2
 2 1
 1 2
 
 5 3 1
 1 2 0 1 2
 0 2
 **/

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