Submission #1034545

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1034545	2024-07-25 14:49:04	dutinmeow	Martian DNA (BOI18_dna)	C++17	100 / 100	69 ms	4692 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 <iostream>
#include <utility>
#include <vector>
int main() {
  int n, k, r;
  std::cin >> n >> k >> r;
  std::vector<int> a(n);
  for (int &x : a)
    std::cin >> x;
  std::vector<int> c(k, 0);
  for (int i = 0; i < r; i++) {
    int h, q;
    std::cin >> h >> q;
    c[h] = q;
  }
  
  int rr = n+1, bl = 0, br = -1, fn = 0;
  std::vector<int> f(k, 0);
  while (bl < n) {
    while (br < n-1 && fn < r) {
      int h = a[++br];
      if (++f[h] == c[h])
        fn++;
    }
    if (fn == r) 
      rr = std::min(rr, br-bl+1);
    int h = a[bl++];
    if (f[h]-- == c[h]) 
      fn--;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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