Submission #659162

#	Time	Username	Problem	Language	Result	Execution time	Memory
659162		600Mihnea	Martian DNA (BOI18_dna)	C++17	100 / 100	28 ms	2448 KiB

dna

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int INF = (int) 1e9 + 7;
int n;
int k;
int r;
int base[N];
int min_quantity[N];
int f[N];

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  ///freopen ("input.txt", "r", stdin);
  cin >> n >> k >> r;
  for (int i = 0; i < n; i++) {
    cin >> base[i];
  }
  for (int i = 0; i < r; i++) {
    int base_id;
    cin >> base_id;
    cin >> min_quantity[base_id];
  }
  int unsolved_restrictions = r;
  int l = 0, sol = INF;
  for (int r = 0; r < n; r++) {
    f[base[r]]++;
    unsolved_restrictions -= (min_quantity[base[r]] > 0 && f[base[r]] == min_quantity[base[r]]);
    if (unsolved_restrictions == 0) {
      while (min_quantity[base[l]] == 0 || f[base[l]] != min_quantity[base[l]]) {
        f[base[l++]]--;
      }
      sol = min(sol, r - l + 1);
    }
  }
  if (sol == INF) {
    cout << "impossible\n";
    return 0;
  }
  cout << sol << "\n";
  return 0;
}

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