제출 #960940

#제출 시각아이디문제언어결과실행 시간메모리
960940batsukh2006 Martian DNA (BOI18_dna)C++17
100 / 100
35 ms6752 KiB
#include<iostream> #include<stdio.h> #include<math.h> #include<map> #include<string> #include<algorithm> #include<vector> #include<string.h> #include<utility> #include<set> #include<cmath> #include<queue> #include<deque> #include<functional> #include<stack> #include<limits.h> #include<iomanip> #include<unordered_map> #include<numeric> #include<tuple> #include<bitset> using namespace std; #define MOD 1000000007 #define int long long #define ss second #define ff first #define endl '\n' typedef pair<int,int> pp; signed main(){ // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k,r; cin>>n>>k>>r; vector<int> a(n+1),mp(k+1,-1),fq(k+1); for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=r; i++){ int b,q; cin>>b>>q; mp[b]=q; } int ans=1e18,sum=0; for(int i=1,j=1; i<=n; i++){ fq[a[i]]++; if(fq[a[i]]==mp[a[i]]&&mp[a[i]]!=-1) sum++; while(sum==r){ ans=min(ans,i-j+1); fq[a[j]]--; if(fq[a[j]]<mp[a[j]]&&mp[a[j]]!=-1) sum--; j++; } } if(ans==1e18) cout<<"impossible"; else cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...