Submission #676145

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
6761452022-12-29 13:36:53LeonaRagingTelefoni (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;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...