oj.uz

Submission #940487

# Submission time Handle Problem Language Result Execution time Memory
940487 2024-03-07T09:53:11 Z irmuun Martian DNA (BOI18_dna) C++17
0 / 100
 2000 ms 30384 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k,r;
    cin>>n>>k>>r;
    int a[n];
    set<int>st[k];
    for(int i=0;i<k;i++){
        st[i].insert(n);
    }
    for(int i=0;i<n;i++){
        cin>>a[i];
        st[a[i]].insert(i);
    }
    vector<bool>need(k,0);
    int b[r],q[r];
    bool ok=true;
    int R=0;
    for(int i=0;i<r;i++){
        cin>>b[i]>>q[i];
        need[b[i]]=true;
        if((int)st[b[i]].size()-1<q[i]){
            cout<<"impossible";
            return 0;
        }
        q[i]--;
        R=max(R,*st[b[i]].begin());
        while(q[i]--){
            st[b[i]].erase(st[b[i]].begin());
            R=max(R,*st[b[i]].begin());
        }
    }
    int ans=n;
    for(int i=0;i<n;i++){
        if(R<n) ans=min(ans,R-i+1);
        if(need[a[i]]==true){
            st[a[i]].erase(st[a[i]].begin());
            if(!st[a[i]].empty()){
                R=max(R,*st[a[i]].begin());
            }
        }
    }
    cout<<ans;
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:27:10: warning: unused variable 'ok' [-Wunused-variable]
   27 |     bool ok=true;
      |          ^~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 10832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 20308 KB Output is correct
2 Correct 69 ms 18112 KB Output is correct
3 Correct 47 ms 17492 KB Output is correct
4 Correct 36 ms 10772 KB Output is correct
5 Correct 74 ms 22116 KB Output is correct
6 Execution timed out 2079 ms 30384 KB Time limit exceeded
7 Halted 0 ms 0 KB -