제출 #970871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970871		pera	Martian DNA (BOI18_dna)	C++17	100 / 100	75 ms	4652 KiB

dna

#include<bits/stdc++.h>
using namespace std;
int n , k , r;
int main(){
   cin >> n >> k >> r;
   vector<int> a(n + 1) , have(k) , want(k);
   for(int i = 1;i <= n;i ++){
      cin >> a[i];
   }
   int is_good = 0;
   for(int i = 1;i <= r;i ++){
      int B , Q;
      cin >> B >> Q;
      want[B] = Q;
   }
   int ans = 1e9 , l = 1;
   for(int i = 1;i <= n;i ++){
      ++have[a[i]];
      is_good += have[a[i]] == want[a[i]];
      while(have[a[l]] - 1 >= want[a[l]] && l <= i){
         --have[a[l]];
         ++l;
      }
      if(is_good == r){
         ans = min(ans , i - l + 1);
      }
   }
   if(ans == 1e9){
      cout << "impossible" << endl;
      return 0;
   }
   cout << ans << endl;
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32