Cod sursa(job #630547)

Utilizator ion824Ion Ureche ion824 Data 5 noiembrie 2011 19:13:32
Problema Deque Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
using namespace std;
struct comb{ int val,pos; }deq[500005];

int main(void){
    ifstream fin("deque.in");
    ofstream fout("deque.out");
    int i,n,k,aux,c1=1,c2=1; 
    long long suma=0;
    fin>>n>>k;
    for(i=1;i<=n;++i){
      fin>>aux;
      if(deq[c1].pos<i-k)++c1;
      if(i>k)suma+=deq[c1].val; 
      if(aux>deq[c2].val){ 
                          deq[++c2].val=aux; 
                          deq[c2].pos=i;                         
                         }
         else{
              while(aux<deq[c2].val && c2>=c1)--c2;
              ++c2;
              deq[c2].val=aux;
              deq[c2].pos=i;                               
              } 
           }
    suma+=deq[c1].val;               
    fout<<suma; fin.close(); fout.close();
 return 0;   
}