Submission #702738

#TimeUsernameProblemLanguageResultExecution timeMemory
702738Shreyan_Paliwal Martian DNA (BOI18_dna)C++17
100 / 100
115 ms4524 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 200000; // R, K <= N const int INF = 2e9; int n, // length of real DNA k, // alphabet size r; // number of minimum quantities int min_quant[maxn]; int cur_quant[maxn]; int dna[maxn]; int current_satisfied; int ans = INF; int main() { // freopen("main.in", "r", stdin); cin >> n >> k >> r; for (int i = 0; i < n; i++) cin >> dna[i]; for (int i = 0; i < r; i++) { int a; cin >> a; cin >> min_quant[a]; } for (int i = 0; i < k; i++) current_satisfied += cur_quant[i] >= min_quant[i]; int l = 0; for (int i = 0; i < n; i++) { // [l, i] inclusive // add new cur_quant[dna[i]]++; if (cur_quant[dna[i]] == min_quant[dna[i]]) current_satisfied++; // remove as many as possible while (current_satisfied == k && l <= i) { ans = min(ans, i - l + 1); if (cur_quant[dna[l]] == min_quant[dna[l]]) current_satisfied--; cur_quant[dna[l]]--; l++; } } if (ans == INF) { cout << "impossible" << endl; return 0; } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...