Submission #1032788

#TimeUsernameProblemLanguageResultExecution timeMemory
1032788anango Martian DNA (BOI18_dna)C++17
100 / 100
61 ms6740 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int INF = 1LL<<30; signed main() { /*#ifdef ONLINE_JUDGE ios_base::sync_with_stdio(false); cin.tie(NULL); #endif*/ //fast IO int n,k,c; cin >> n >> k >> c; vector<int> ar(n); for (int i=0; i<n; i++) cin >> ar[i]; vector<int> freq(k,0); vector<int> req(k,0); for (int i=0; i<c; i++) { int a,b; cin >> a >> b; req[a] = b; } int unsatisfied = 0; for (int i=0; i<k; i++) unsatisfied+=req[i]>0; int r = -1; int ans = INF; for (int l=0; l<n; l++) { while (unsatisfied>0 && r<n-1) { r++; freq[ar[r]]++; unsatisfied-=freq[ar[r]]==req[ar[r]]; } //cout << l <<" " << r <<" " << unsatisfied << endl; if (unsatisfied==0) { ans=min(ans,r-l+1); } unsatisfied+=freq[ar[l]]==req[ar[l]]; freq[ar[l]]--; } if (ans<INF) cout << ans << endl; else cout << "impossible" << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...