Submission #676145

#TimeUsernameProblemLanguageResultExecution timeMemory
676145LeonaRagingTelefoni (COCI17_telefoni)C++14
80 / 80
17 ms1776 KiB
#include <bits/stdc++.h> using namespace std; #define db(val) "[" #val " = " << (val) << "] " const int maxn = 3e5 + 4; int n, d, nxt[maxn]; bool a[maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> d; for (int i = 1; i <= n; i++) cin >> a[i]; queue<int> q; for (int i = n; i >= 1; i--) { while (!q.empty() && q.front() > i + d) q.pop(); nxt[i] = (!q.empty() ? q.front() : 0); if (a[i]) q.push(i); } int cur = 1, res = 0; while (cur < n) { if (nxt[cur]) cur = nxt[cur]; else res++, cur = cur + d; } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...