Submission #1326193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326193		islam_2010	Martian DNA (BOI18_dna)	C++20	0 / 100	331 ms	17008 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define int long long

map<int, int> mp, mp2, mp3;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, m;
    cin >> n >> k >> m;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp3[a[i]]++;
    }int cm = m;
    while (cm--){
        int u, v;
        cin >> u >> v;
        mp2[u] = v;
    }bool ok = false;
    for(auto i: mp2){
        ok |= (mp3[i.first] < i.second);
    }if(ok){
        cout << "impossible";
        return 0;
    }
    int l = 0;
    int r = 0;
    int c = 0;
    for(int i = 0; i < n; i++){
        mp[a[i]]++;
        if(mp2.count(a[i])){
            if(mp[a[i]] == mp2[a[i]]){
                c++;
            }if(c == m){
                r = i;
                break;
            }
        }
    }
    int mn = INT_MAX;
    while(l < r){
        if(mp[a[l]] > mp2[a[l]]){
            mp[a[l]]--;
            l++;
            
        }else {
            break;
        }
    }
    mn = min(mn, r-l+1);

    for(int i = r+1; i < n; i++){
        int num;
        int c = 0;
        while(l < i){
            mp[a[l]]--;
            if(mp[a[l]] < mp2[a[l]]){

                num = a[l];
                l++;
                break;
            }l++;
        }while(i < n){
            if(mp[num] < mp2[num]){
                mp[a[i++]]++;
                
            }else {
                break;
            }
        }while(l < i){
            if(mp[a[l]] > mp2[a[l]]){
                mp[a[l]]--;
                l++;
            }else {
                break;
            }
        }
        mn = min(mn, i-l);
    }
    cout << mn << endl;
    
}

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