Cod sursa(job #679448)
Utilizator | zloteanu adrian nichita zloteanu.adrian | Data | 13 februarie 2012 11:49:52 |
---|---|---|---|
Problema | Deque | Scor | 5 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include<fstream>
using namespace std;
int k,st=-1,dr,v[5000001],d[5000001],n,s;
inline void dreapta(int i) {
while(st<=dr&&v[i]<=v[d[dr]])
dr--;
d[++dr] = i;
}
inline void stanga(int i) {
if(d[st]==i-k) {
st++;
}
}
int main()
{
ifstream q("deque.in");
ofstream w("deque.out");
q>>n>>k;
for(int i=1;i<=n;i++)
{
q>>v[i];
}
for(int i=1;i<=n;i++)
{
if(i>k)
stanga(i);
dreapta(i);
//w << i << " -> " << v[d[st]] << "\n";
if(i>=k) s+=v[d[st]];
}
w<<s;
}