제출 #1132558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132558		codexistent	Martian DNA (BOI18_dna)	C++20	100 / 100	98 ms	17544 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXNRK 200005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n, k, r, b[MAXNRK], tidx[MAXNRK], rq[MAXNRK];
vector<ll> toc[MAXNRK];
stack<ll> st;
ll ans = LLONG_MAX;

void printans(){
    if(ans == LLONG_MAX) cout << "impossible" << endl;
    else cout << ans << endl;
}

int main(){
    cin >> n >> k >> r;
    FOR(i, 1, n) {
        cin >> b[i];
        toc[b[i]].push_back(i);
        rq[i - 1] = 0, tidx[i - 1] = -1;

        if(i <= k) st.push(i - 1);
    }
    FOR(i, 1, r){
        ll x; cin >> x;
        cin >> rq[x];
    }

    ll i2 = 0;
    FOR(i, 1, n){
        while(st.size()){
            ll sti = st.top(); st.pop();
            while(rq[sti] > 0){
                if(tidx[sti] + 1 >= toc[sti].size()){
                    printans();
                    return 0;
                }
                rq[sti]--;

                tidx[sti]++;
                i2 = max(i2, toc[sti][tidx[sti]]);
            }
        }

        ans = min(ans, 1 + i2 - i);

        rq[b[i]]++; 
        st.push(b[i]);
    }
    printans();
}

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