Submission #314018

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
314018	2020-10-17 21:17:30	sofapuden	Martian DNA (BOI18_dna)	C++14	100 / 100	38 ms	2688 KiB

dna

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, k, r; cin >> n >> k >> r;
  vector<int> v(n);
  for(auto &x : v)cin >> x;
  vector<int> ha(k,0), wa(k,0);
  for(int i = 0; i < r; ++i){
    int a, b; cin >> a >> b;
    wa[a] = b;
  }
  int l = -1, ri = -1, go = 0, best = 1<<30;
  while(++ri < n){
    ha[v[ri]]++;
    if(ha[v[ri]] == wa[v[ri]])go++;
    if(go == r){
      while(go == r){
        ++l;
        ha[v[l]]--;
        if(ha[v[l]] == wa[v[l]]-1)go--;
      }
      best = min(best,ri-l+1);
    }
  }
  cout << (best == (1<<30) ? "impossible" : to_string(best)) << "\n";
    
    
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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