Submission #675956

#	Time	Username	Problem	Language	Result	Execution time	Memory
675956		browntoad	Martian DNA (BOI18_dna)	C++14	100 / 100	36 ms	5036 KiB

dna

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define f first
#define s second
#define pb push_back
 
const ll maxn = 2e5+5;
const ll inf = (1ll<<60);
 
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k, r; cin>>n>>k>>r;
    vector<int> req(k), cur(k);
    vector<int> vc(n);
    REP(i, n){
        cin>>vc[i];
    }
    REP(i, r){
        int a, b; cin>>a>>b;
        req[a]=b;
    }
    r=-1;
    int cpos = 0;
    REP(i, n){
        cur[vc[i]]++;
        while(cpos<k&&req[cpos]<=cur[cpos]){
            cpos++;
        }
        if (cpos==k){
            r=i;
            break;
        }
    }
    if (r==-1){
        cout<<"impossible"<<endl;
        return 0;
    }
    int ans=inf;
    cpos=-1;
    REP(i, n){
        ans=min(ans, r-i+1);
        cur[vc[i]]--;
        if (cur[vc[i]]<req[vc[i]]){
            cpos=vc[i];
            r++;
            while(r<n){
                cur[vc[r]]++;
                if (cur[cpos]>=req[cpos]){
                    break;
                }
                r++;
            }
            if (r==n){
                break;
            }
        }
    }
    cout<<ans<<endl;
}

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