oj.uz

Submission #993888

# Submission time Handle Problem Language Result Execution time Memory
993888 2024-06-06T18:17:39 Z AndrijaM Martian DNA (BOI18_dna) C++17
0 / 100
 21 ms 8740 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=2e5+10;
const int mod=1e9+7;

int m[maxn];
int cnt[maxn];
int K[maxn];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(m,-1,sizeof m);
    ///freopen("prieteni.in","r",stdin);
    ///freopen("prieteni.out","w",stdout);
    int n,k,r;
    cin>>n>>k>>r;
    int x[n];
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        K[x[i]]++;
    }
    bool T=true;
    for(int i=0;i<r;i++)
    {
        int koj,kol;
        cin>>koj>>kol;
        m[koj]=kol;
        if(K[koj]<m[koj])
        {
            T=false;
        }
    }
    if(!T)
    {
        cout<<"impossible"<<endl;
    }
    int ok=0;
    int ans=n;
    int j=-1;
    for(int i=0;i<n;i++)
    {
        cnt[x[i]]++;
        if(cnt[x[i]]==m[x[i]])
        {
            ok++;
        }
        if(ok==r)
        {
            while(j+1<i && cnt[x[j+1]]!=m[x[j+1]])
            {
                cnt[x[j+1]]--;
                j++;
            }
            ans=min(ans, i-(j+1)+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 3064 KB Output is correct
3 Correct 1 ms 2680 KB Output is correct
4 Incorrect 1 ms 2908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2928 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Incorrect 1 ms 2908 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4700 KB Output is correct
2 Correct 10 ms 4696 KB Output is correct
3 Correct 10 ms 4700 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 15 ms 7768 KB Output is correct
6 Correct 10 ms 4700 KB Output is correct
7 Incorrect 9 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8280 KB Output is correct
2 Correct 21 ms 8276 KB Output is correct
3 Correct 16 ms 7772 KB Output is correct
4 Correct 9 ms 4724 KB Output is correct
5 Incorrect 21 ms 8740 KB Output isn't correct
6 Halted 0 ms 0 KB -