Submission #932928

#TimeUsernameProblemLanguageResultExecution timeMemory
932928asdasdqwer Martian DNA (BOI18_dna)C++14
100 / 100
89 ms4924 KiB
#include <bits/stdc++.h> using namespace std; signed main() { int n,k,r;cin>>n>>k>>r; vector<int> a(n); for (auto &x:a)cin>>x; vector<int> req(n, 0); for (int i=0;i<r;i++) { int c1,c2;cin>>c1>>c2; req[c1] += c2; } vector<int> cnt(n, 0); for (auto &x:a)cnt[x]++; for (int i=0;i<n;i++) { if (req[i] > cnt[i]) { cout<<"impossible\n"; return 0; } } int p1 = 0, p2 = -1; int sat = 0; cnt.assign(n,0); for (; p1 < n; p1++) { cnt[a[p1]]++; if (cnt[a[p1]] == req[a[p1]]) { sat++; } if (sat == r) { break; } } int minLen = p1 - p2; for (; p1<n;) { while (p2+1 < n && cnt[a[p2+1]]-1 >= req[a[p2+1]]) { p2++; cnt[a[p2]]--; } minLen = min(minLen, p1-p2); p1++; if (p1 != n) { cnt[a[p1]]++; } } cout<<minLen<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...