Cod sursa(job #1609329)
Utilizator | Data | 22 februarie 2016 18:52:52 | |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.4 kb |
#include <fstream>
using namespace std;
ifstream fi("deque.in");
ofstream fo("deque.out");
int v[5000001], d[5000001];
int main()
{
int n, k, i, p, q, sum = 0;
fi >> n >> k;
p = q = 1;
d[p] = 1;
sum = 0;
for (i = 2; i <= n; i++)
{
//intra v[i]
while (p <= q && v[d[q]] >= v[i]) q--;
q++;
d[q] = i;
if (d[p] < i - k + 1)p++;
sum += v[d[p]];
}
fo << sum;
}