Submission #941134

#TimeUsernameProblemLanguageResultExecution timeMemory
941134FKS Martian DNA (BOI18_dna)C++14
100 / 100
139 ms16768 KiB
#include <bits/stdc++.h> using namespace std; #define max(a, b) (a > b ? a : b) int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, r;cin>>n>>k>>r; int* dna = new int[n]; for (int i = 0;i < n;i++) cin >> dna[i]; unordered_set<int> hset; unordered_map<int, int> req; unordered_set<int> sreq; for (int i = 0;i < r;i++) { int x, y; cin >> x >> y; hset.emplace(x); req[x] = y; sreq.emplace(x); } int min_len = 1e9; int j = -1; for (int i = 0;i < n;i++) { if (i && hset.count(dna[i-1])) { req[dna[i-1]]++; if (req[dna[i-1]] > 0) sreq.emplace(dna[i-1]); } if (sreq.size()) for (j=j+1;j < n;j++) { if (hset.count(dna[j])) { req[dna[j]]--; if (req[dna[j]] <= 0) sreq.erase(dna[j]); } if (!sreq.size()) { min_len = min(min_len, j - i + 1); break; } } else min_len = min(min_len, j - i + 1); } if (min_len == 1e9) cout << "impossible"; else if (min_len) cout << min_len; else if (min_len == 0) cout << "impossible"; 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...