제출 #1326507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326507		islam_2010	Martian DNA (BOI18_dna)	C++20	100 / 100	355 ms	36548 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]]++;
    }for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        mp2[u] = v;
    }bool ok = true;
    for(auto i: mp2){
        if(mp3[i.first] < i.second){
            ok = false;
            break;
        }
    }if(!ok){
        cout << "impossible";
        return 0;
    }int l = 0, r = 0, c = 0, mn = INT_MAX;
    for(int i = 0; i < n; i++){
        mp[a[i]]++;
        if(mp[a[i]] == mp2[a[i]]){
            c++;
            if(c == m){
                r = i;
                break;
            }
        }
    }while(l < r){
        if(mp[a[l]] > mp2[a[l]]){
            
            mp[a[l]]--;
            l++;
        }else {
            break;
        }
        
    }mn = min(mn, r-l+1);
    c = 0;
    r++;

    while (r < n){
        mp[a[l]]--;
        c = 0;
        int num;
        if(mp2[a[l]] > mp[a[l]]){
            c = 1;
            num = a[l];
        }l++;
        if(!c){
            mn = min(mn, r-l+1);
        }
        bool ok = false;
        if(c){
            while(r < n){
                if(mp[num] < mp2[num]){
                    mp[a[r]]++;
                    
                    if(mp[num] >= mp2[num]){
                        ok = true;
                        mp[a[r]]--;
                        break;
                    }
                    r++;
                    
                }else {
                    break;
                }
            }
        }if(ok){
            mn = min(mn, r-l+1);
        }
    }cout << mn;
    
}

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