Cod sursa(job #2000617)
Utilizator | Frinculeasa Alexandru Frincu | Data | 14 iulie 2017 11:45:04 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.69 kb |
#include <iostream>
#include <fstream>
using namespace std;
int main()
{ long long s=0;
int n,k,i,st,fn,j;
int * p,* q;
p=new int [5000000];
q=new int [5000000];
ifstream f("deque.in");
ofstream g("deque.out");
f>>n>>k;
for(i=0;i<n;i++)
f>>p[i];
j=0;
q[0]=0;
st=0;
for(i=1;i<k;i++)
{
while(j>=st && p[i]<=p[q[j]])
j--;
q[++j]=i;
}
fn=j;
s=s+p[q[st]];
for(i=k;i<n;i++)
{
while(j>=st && p[i]<=p[q[j]])
j--;
q[++j]=i;
if(i-k+1>q[st])st++;
s=s+p[q[st]];
}
g<<s;
delete p;
delete q;
return 0;
}