Cod sursa(job #811703)
| Utilizator | Data | 12 noiembrie 2012 20:44:49 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
#include <utility>
#include <queue>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int a, n, i, j, k;
long long s;
deque<pair<int,int> > m;
int main() {
in>>n>>k;
for(i=1; i<=n; i++) {
in>>a;
while(!m.empty() && m.back().first >= a) {
m.pop_back();
}
m.push_back(make_pair(a, i));
while(m.front().second <= i-k)
m.pop_front();
if(i >= k) {
s += m.front().first;
}
}
out<<s;
return 0;
}
