Submission #1096082

#TimeUsernameProblemLanguageResultExecution timeMemory
1096082andrewp Martian DNA (BOI18_dna)C++14
68 / 100
34 ms18012 KiB
//Dedicated to my love, ivaziva #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using ll = int64_t; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define pb push_back #define dbg(x) cerr<<#x<<": "<<x<<'\n'; #define dbga(A,l_,r_){for(int i_=l_;i_<=r_;i_++)cerr<<A[i_]<<' ';cerr<<'\n';} #define dbgv(a_){for(auto x_:a_) cerr<<x_<<' ';cerr<<'\n';} const int maxn = 2e5 + 3; int n, k, r; int a[maxn], b[maxn], q[maxn], ps[maxn][20]; bool check(int len) { for (int i = len; i <= n; i++) { bool ok = true; for (int j = 1; j <= r; j++) { if (ps[i][j] - ps[i - len][j] < q[j]) { ok = false; } } if (ok) { return true; } } return false; } void reshi1() { for (int j = 1; j <= r; j++) { ps[0][j] = 0; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= r; j++) { ps[i][j] = ps[i - 1][j] + (a[i] == b[j]); } } int l = 1, r = n, ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { r = mid - 1; ans = mid; } else { l = mid + 1; } } if (ans == -1) { cout << "impossible\n"; return; } cout << ans << '\n'; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); cin >> n >> k >> r; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= r; i++) { cin >> b[i] >> q[i]; } if (r <= 450) { reshi1(); return 0; } 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...