Submission #1013741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013741		vjudge1	Martian DNA (BOI18_dna)	C++17	0 / 100	12 ms	4956 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
#define int long long
const long long inf=1e18;
const int MOD=998244353;
const int N=3e5+5;
int req[4];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,k,r; cin>>n>>k>>r;
    int a[n],l=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<r;i++){
        int x,y; cin>>x>>y;
        req[x]=y;
    }
    int cnt0=0,cnt1=0,cnt2=0,cnt3=0,ans=inf;
    for(int i=0;i<n;i++){
        if(a[i]==0)cnt0++;
        if(a[i]==1)cnt1++;
        if(a[i]==2)cnt2++;
        if(a[i]==3)cnt3++;
        while(l<i){
            if(req[0]>cnt0 || req[1]>cnt1 || req[2]>cnt2 || req[3]>cnt3)break;
            if(a[l]==0)cnt0--;
            if(a[l]==1)cnt1--;
            if(a[l]==2)cnt2--;
            if(a[l]==3)cnt3--;
            l++;
            if(req[0]>cnt0 || req[1]>cnt1 || req[2]>cnt2 || req[3]>cnt3){
                l--;
                if(a[l]==0)cnt0++;
                if(a[l]==1)cnt1++;
                if(a[l]==2)cnt2++;
                if(a[l]==3)cnt3++;
                break;
            }
        }
        if(req[0]<=cnt0 && req[1]<=cnt1 && req[2]<=cnt2 && req[3]<=cnt3){
            ans=min(ans,i-l+1);
        }
    }
    if(ans==inf)cout<<"impossible";
    else cout<<ans;
}

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