Cod sursa(job #3127304)
Utilizator | Data | 7 mai 2023 14:25:11 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.57 kb |
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int main()
{
int n, k;
long long int s=0;
f>>n>>k;
int *d = new int[5000001], *a = new int[5000001];
int st = 1, dr = 0;
for(int i=1; i<=n; i++)
f>>a[i];
for(int i=1; i<=n; i++){
while(a[i] <= a[d[dr]] && st <= dr)
dr--;
dr++;
d[dr] = i;
if(d[st] <= i-k)
st++;
if(i >= k)
s += a[d[st]];
}
g<<s;
return 0;
}