Submission #1268696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268696		rtri	Martian DNA (BOI18_dna)	C++20	100 / 100	74 ms	1864 KiB

dna

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k, r;
  cin >> n >> k >> r;

  vector<int> dna(n);
  for (int i = 0; i < n; i++)
    cin >> dna[i];

  vector<int> req(k, -1e9);
  for (int i = 0; i < r; i++) {
    int b, q;
    cin >> b >> q;
    req[b] = q;
  }

  int satisfied_count = 0;
  for (int i = 0; i < k; i++)
    if (req[i] < 0)
      satisfied_count++;

  int shortest = 1e9;
  int right = 0;
  for (int left = 0; left < n; left++) {
    while (right < n && satisfied_count != k) {
      req[dna[right]]--;
      if (req[dna[right]] == 0)
        satisfied_count++;

      right++;
    }

    if (satisfied_count == k && right - left < shortest) {
      shortest = right - left;
    }

    req[dna[left]]++;
    if (req[dna[left]] == 1)
      satisfied_count--;
  }

  if (shortest == 1e9)
    cout << "impossible" << endl;
  else
    cout << shortest << endl;

  return 0;
}

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