Cod sursa(job #3188824)
Utilizator | Rusu Luca Alexinfo22 | Data | 3 ianuarie 2024 21:33:45 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.46 kb |
#include <fstream>
#include<deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int n,k,a[5000001],st,dr,q[5000001];
long long s;
int main()
{ fin>>n>>k;
for(int i=1;i<=n;i++)
fin>>a[i];
st=1,dr=0;
for(int i=1;i<=n;i++)
{
while(st<=dr && a[i]<=a[q[dr]])
dr--;
q[++dr]=i;
if(q[st]==i-k) st++;
if(i>=k) s+=a[q[st]];
}
fout<<s;
return 0;
}