Cod sursa(job #3137671)
Utilizator | Mironov Cezar Luca Carena | Data | 14 iunie 2023 11:47:38 |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
#define NMAX 5000000
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
int dq[NMAX], v[NMAX];
int st=0, dr=-1;
void baga(int poz)
{
while(v[poz]<=v[dq[dr]] && dr>=st)
dr--;
dq[++dr]=poz;
}
void scoate(int poz)
{
if(dq[st]==poz)
st++;
}
int main()
{
int n, k, i;
long long s=0;
cin>>n>>k;
for(i=1;i<=n;i++)
cin>>v[i];
for(i=1;i<k;i++)
baga(i);
for(i=k;i<=n;i++)
{
baga(i);
s+=v[dq[st]];
scoate(i-k+1);
}
cout<<s;
return 0;
}