Nu aveti permisiuni pentru a descarca fisierul grader_test9.ok
Cod sursa(job #2563901)
| Utilizator | Data | 1 martie 2020 15:57:33 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.69 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
deque<pair<int,int> > deq;
long long n,k,a,sum,i;
int main()
{
fin>>n>>k;
for(i=0; i<k; i++)
{
fin>>a;
while(!deq.empty() && deq.back().first>=a) deq.pop_back();
deq.push_back(make_pair(a,i));
}
sum+=deq.front().first;
for(i=k; i<n; i++)
{
fin>>a;
while(!deq.empty() && deq.back().first>=a) deq.pop_back();
deq.push_back(make_pair(a,i));
if(deq.front().second<=i-k)
{
deq.pop_front();
}
sum+=deq.front().first;
}
fout<<sum;
return 0;
}
