Cod sursa(job #3225817)
Utilizator | Cristea David DavidCristea | Data | 19 aprilie 2024 09:31:47 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.69 kb |
#include <fstream>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
int v[5000005],coada[5000005];
int main()
{
int n,k,i,sf=0,inc=1;
long long s=0;
cin>>n>>k;
for(i=1; i<=n; i++)
{
cin>>v[i];
if(i<k)
{
while(sf>=inc && v[i]<v[coada[sf]])
sf--;
sf++;
coada[sf]=i;
}
else
{
if(i-k+1>coada[inc])
inc++;
while(sf>=inc && v[i]<v[coada[sf]])
sf--;
sf++;
coada[sf]=i;
s=s+v[coada[inc]];
}
}
cout<<s;
return 0;
}