Cod sursa(job #484963)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 16 septembrie 2010 17:18:10
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <deque>
#include<vector>
using namespace std;

deque<pair<long,long> >Q;
int main()
{
    long long i,n,k,s,a;
    ifstream fi("deque.in");
    ofstream fo("deque.out");
    fi>>n>>k;
    for(i=1;i<=k-1;i++)
    {
      fi>>a;
      while(!Q.empty())
      {
         if(Q.back().first>=a)
         Q.pop_back(); else break;
      }
      Q.push_back(make_pair(a,i));
    }
    s=0;
    for(i=k;i<=n;i++)
    {
      fi>>a;
      while(!Q.empty())
      {
      if(Q.back().first>=a)
         Q.pop_back(); else break;
      }
      Q.push_back(make_pair(a,i));
      s+=Q.front().first;
      if(Q.front().second<=i-k+1) Q.pop_front();
    }
    fo<<s<<"\n";
    return 0;
}