Submission #884402

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
884402	2023-12-07 09:46:54	lalig777	Telefoni (COCI17_telefoni)	C++14	80 / 80	45 ms	1624 KiB

telefoni

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
  int n, d;
  cin>>n>>d;
  vector<int>telefoni(n);
  priority_queue<pair<int,int>, vector<pair<int, int> >, greater<pair<int,int> > >pq;
  pq.push(make_pair(0, 0));
  cin>>telefoni[0];
  telefoni[0]=0;
  for (int i=1; i<n; i++){
    cin>>telefoni[i];
    if (telefoni[i]==0) telefoni[i]=1;
    else telefoni[i]=0;
    while (!pq.empty()){
      if (i-pq.top().second>d) pq.pop();
      else{
        telefoni[i]+=pq.top().first;
        pq.push(make_pair(telefoni[i], i));
        break;
      }
    }
  }cout<<telefoni[n-1]<<endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 80 / 80