Submission #1367085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367085		nini_gvenetadze	Martian DNA (BOI18_dna)	C++20	100 / 100	49 ms	2728 KiB

dna

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, k, r;
    cin>>n>>k>>r;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    vector<int> g(k+1, 0);
    for(int i=0; i<r; i++)
    {
        int x, y;
        cin>>x>>y;
        g[x]=y;
    }
    int l=1; int m=0, ans=INT_MAX;
    vector<int> vec(k+1, 0);
    for(int i=1; i<=n; i++)
    {
           vec[a[i]]++;
           if(g[a[i]]>0 && vec[a[i]]==g[a[i]]) m++;
           while(m==r)
           {
                  ans=min(ans, i-l+1);
                  vec[a[l]]--;
                  if(g[a[l]]>0 && vec[a[l]]<g[a[l]])
                  {
                    m--;
                  }
                  l++;
           }
    }
    if(ans==INT_MAX) {cout<<"impossible"<<endl;}
    else
    cout<<ans<<endl;
}

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