Cod sursa(job #2046115)
Utilizator | Rosu Diana Michesa dianamichesa | Data | 23 octombrie 2017 14:39:23 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
const int N=5000001;
int v[N],d[N];
long long s;
int n,k,st,dr=-1;
int main()
{
f>>n>>k;
for(int i=0;i<n;i++){
f>>v[i];
if(st<=dr && d[st]==i-k)
++st;
while(st<=dr && v[i]<=v[d[dr]])
--dr;
d[++dr]=i;
if(i>=k-1)
s+=v[d[st]];
/*for(int j=st;j<=dr;j++)
g<<v[d[j]]<<' ';
g<<'\n';*/
}
g<<s;
return 0;
}