Pagini recente » Cod sursa (job #738139) | Cod sursa (job #2340488) | Cod sursa (job #2110499) | Cod sursa (job #38772) | Cod sursa (job #2264828)
//
// main.cpp
// Deque
//
// Created by Darius Buhai on 20/10/2018.
// Copyright © 2018 Darius Buhai. All rights reserved.
//
#include <iostream>
#include <deque>
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int n, k, x, s;
deque<pair<int, int>> v;
/// tinem minte elementele in ordine crescatoare
/// Ex: 3 1 4 5 7 9 10 6 9
/// [3] -> [(1) 4 5]
/// [(1) 4 5 7]
/// [(4) 5 7 9 10]
/// [(5) 6]
/// [(6) 9]
/// rez: [1 1 4 5 6]
void rez_deque()
{
fin>>n>>k;
for(int i=0;i<n;i++){
fin>>x;
while(!v.empty() && x<v.back().second)
v.pop_back();
pair<int,int> xx(i,x);
v.push_front(xx);
if(i-v.front().first>=k-1)
v.pop_front();
if(i>=k-1)
s+=v.front().second;
}
fout<<s;
}
int main() {
rez_deque();
return 0;
}