Cod sursa(job #2054936)
Utilizator | Vlad Safta vladsft | Data | 2 noiembrie 2017 18:04:18 |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include <fstream>
using namespace std;
long long v[5000001], d[5000001];
ifstream f("deque.in");
ofstream g("deque.out");
int main()
{
long long st = 0, dr = -1, n, k;
long long sum = 0;
f >> n >> k;
for (int i = 0; i < n; i++)
{
f >> v[i];
if (st <= dr && d[st] == i - k)
st++;
while (st <= dr && v[i] <= v[d[dr]])
dr--;
d[++dr] = i;
if (i >= k-1)
sum += v[d[st]];
}
g << sum;
return 0;
}