Submission #1022409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022409		vjudge1	Martian DNA (BOI18_dna)	C++98	0 / 100	95 ms	8388 KiB

dna

#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits>
using namespace std;

int main() {
    int N, K, R;
    cin >> N >> K >> R;
    
    vector<int> DNA(N);
    for (int i = 0; i < N; ++i) {
        cin >> DNA[i];
    }
    
    unordered_map<int, int> required;
    for (int i = 0; i < R; ++i) {
        int B, Q;
        cin >> B >> Q;
        required[B] = Q;
    }
    
    int left = 0, right = 0;
    int satisfied = 0;
    vector<int> count(K, 0);
    int min_length = numeric_limits<int>::max();
    
    while (right < N) {
        if (required.find(DNA[right]) != required.end()) {
            if (count[DNA[right]] < required[DNA[right]]) {
                ++count[DNA[right]];
                if (count[DNA[right]] == required[DNA[right]]) {
                    ++satisfied;
                }
            }
        }
        
        while (satisfied == R) {
            int current_length = right - left + 1;
            if (current_length < min_length) {
                min_length = current_length;
            }
            
            if (required.find(DNA[left]) != required.end()) {
                --count[DNA[left]];
                if (count[DNA[left]] < required[DNA[left]]) {
                    --satisfied;
                }
            }
            ++left;
        }
        
        ++right;
    }
    
    if (min_length == numeric_limits<int>::max()) {
        cout << "impossible" << endl;
    } else {
        cout << min_length << endl;
    }
    
    return 0;
}

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