답안 #1034545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034545	2024-07-25T14:49:04 Z	dutinmeow	Martian DNA (BOI18_dna)	C++17	100 / 100	69 ms	4692 KB

dna

#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--;
  }
  
  if (rr == n+1)
    std::cout << "impossible\n";
  else
    std::cout << rr << '\n';
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	1468 KB	Output is correct
2	Correct	18 ms	1372 KB	Output is correct
3	Correct	21 ms	1608 KB	Output is correct
4	Correct	18 ms	1536 KB	Output is correct
5	Correct	45 ms	2744 KB	Output is correct
6	Correct	18 ms	1592 KB	Output is correct
7	Correct	20 ms	1724 KB	Output is correct
8	Correct	36 ms	4032 KB	Output is correct
9	Correct	27 ms	2140 KB	Output is correct
10	Correct	18 ms	1476 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	448 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	344 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	3512 KB	Output is correct
2	Correct	47 ms	3112 KB	Output is correct
3	Correct	37 ms	2896 KB	Output is correct
4	Correct	18 ms	1368 KB	Output is correct
5	Correct	69 ms	3924 KB	Output is correct
6	Correct	61 ms	4692 KB	Output is correct
7	Correct	29 ms	2140 KB	Output is correct
8	Correct	34 ms	2396 KB	Output is correct
9	Correct	17 ms	1628 KB	Output is correct
10	Correct	18 ms	1372 KB	Output is correct
11	Correct	27 ms	1600 KB	Output is correct
12	Correct	19 ms	1628 KB	Output is correct
13	Correct	37 ms	2900 KB	Output is correct
14	Correct	19 ms	1628 KB	Output is correct
15	Correct	20 ms	1596 KB	Output is correct
16	Correct	35 ms	4024 KB	Output is correct
17	Correct	28 ms	2140 KB	Output is correct
18	Correct	17 ms	1620 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	436 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct