oj.uz

Submission #659161

# Submission time Handle Problem Language Result Execution time Memory
659161 2022-11-16T20:06:32 Z 600Mihnea Martian DNA (BOI18_dna) C++17
0 / 100
 26 ms 1620 KB 
#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 = k;
  int l = 0, sol = INF;
  for (int r = 0; r < n; r++) {
    f[base[r]]++;
    unsolved_restrictions -= (f[base[r]] == min_quantity[base[r]]);
    if (unsolved_restrictions == 0) {
      while (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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -