Submission #1194332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194332		teletubigam3	Martian DNA (BOI18_dna)	C++20	0 / 100	18 ms	2376 KiB

dna

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define se second
#define pb push_back
#define fi first
#define fo(var, n) for(long long var=0;var<n;var++)
#define fore(var, n) for(long long var=n-1;var>=0;var--)
using namespace std;
using ll = long long;


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    int tt = 1;
    //cin>>tt;

    while(tt--)
    {
        int n,k,r; cin>>n>>k>>r;
        int a[n];
        fo(i,n) cin>>a[i];
        int b[k];
        fo(i,k) b[i]=0;
        fo(i,r)
        {
            int t,c; cin>>t>>c;
            b[t] = c;
        }
        int i = 0,j=0;
        int c[k];
        fo(i,k) c[i] = 0;
        int hav=0;
        int ans=1e8;
        while(i< n && j<n)
        {
            while(i<n && hav != r)
            {
                c[a[i]] ++; if(c[a[i]] == b[a[i]]) hav++; i++;
            }
            while(j<n)
            {
                if(c[a[j]] == b[a[j]]) break;
                c[a[j]] --; j++;
            }
            if(j == n) break;
            ans=min(ans, i-j);
            c[a[j]] --; j++;
            hav--;
        }
        if(ans == 1e8) cout<<"impossible\n";
        else cout<<ans<<"\n";

    }



    return 0;
}

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