Submission #391590

#	Time	Username	Problem	Language	Result	Execution time	Memory
391590		Victor	Martian DNA (BOI18_dna)	C++17	100 / 100	69 ms	4676 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trax(a, x) for (auto& a : x)
#define sz(a) a.size()
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, k, r, quant[200001], dna[200001];
    memset(quant, 0, sizeof(quant));
    cin >> n >> k >> r;
    rep(i, 0, n) cin >> dna[i];
    rep(i, 0, r) {
        int b, q;
        cin >> b >> q;
        quant[b] = q;
    }

    int lo = 1, hi = n+1;
    vi curr,dummy(n,0);

    while (lo < hi) {
        int mid = (hi + lo) >> 1,have=0;
        curr=dummy;
        bool work=0;

        rep(i, 0, mid - 1){
            int base=dna[i];
            if(++curr[base]==quant[base])++have;
        }

        rep(i,mid-1,n){
            int base=dna[i];
            ++curr[base];
            if(curr[base]==quant[base])++have;

            if(have==r){
                work=1;
                break;
            }

            base=dna[i-mid+1];
            if(quant[base]==curr[base])--have;
            --curr[base];
        }

        if(work)hi=mid;
        else lo=mid+1;
    }

    if(n<lo)cout<<"impossible"<<endl;
    else cout<<lo<<endl;
}

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