Cod sursa(job #775925)
Utilizator | Georgescu Dan cameleon | Data | 9 august 2012 12:34:43 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include<fstream>
using namespace std;
#define NMAX 5000005
ifstream f("deque.in");
ofstream g("deque.out");
int dq[NMAX],a[NMAX],n,k,x,y;
long long sum;
int main()
{
f>>n>>k>>a[1];
int u,p=u=1;dq[p]=a[1];
for(int i=2;i<=k;++i)
{
f>>a[i];
while(a[i]<dq[u]&& p<=u)u--;
dq[++u]=a[i];
}
sum+=dq[p];
for(int i=k+1;i<=n;++i)
{
y=a[i-k];
f>>a[i];
if(dq[p]==y)p++;
if(p<=u){
while(a[i]<dq[u]&& p<=u)u--;
dq[++u]=a[i];
}
else {dq[p]=a[i];u=p;}
sum+=dq[p];
}
g<<sum;
return 0;
}