Pagini recente » Cod sursa (job #596958) | Cod sursa (job #1769697) | Cod sursa (job #1537058) | Cod sursa (job #3155090) | Cod sursa (job #533747)
Cod sursa(job #533747)
// http://infoarena.ro/problema/deque
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
vector<int> number;
deque<int> myQueue;
int main() {
int nrNumbers; // cate numere sunt in fisierul de intrare
int lenght; // lungimea subsecventei
int sum = 0;
int tmp;
in >> nrNumbers >> lenght;
number.push_back(0);
for(int i=1;i<=nrNumbers;i++) {
in >> tmp;
number.push_back(tmp);
}
for(int currentPosition=1;currentPosition<=nrNumbers;currentPosition++) {
while(!myQueue.empty() && myQueue.front() <= myQueue.back() && number[currentPosition] <= number[myQueue.back()])
myQueue.pop_back();
myQueue.push_back(currentPosition);
if(myQueue.front() == currentPosition - lenght)
myQueue.pop_front();
if(currentPosition >= lenght)
sum = sum + number[myQueue.front()];
}
out << sum << "\n";
return (0);
}