Cod sursa(job #965685)

Utilizator Anca_PaneaPanea Anca Anca_Panea Data 24 iunie 2013 14:42:58
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
using namespace std;
#include<fstream>
#include<deque>
ifstream eu("branza.in");
ofstream tu("branza.out");
#define Nmax 100100
long long N, S, T;
long long C[Nmax],P[Nmax],sol;
deque< pair<int,int> > Q;

int main()
{
  eu>>N>>S>>T;
  for (int i=1;i<=N;++i)
  {
    eu>>C[i]>>P[i];
    if(!Q.empty() && i-Q.front().second>T)
      Q.pop_front();
    while(!Q.empty() && Q.back().first+(i-Q.back().second)*S>C[i])
      Q.pop_back();
    Q.push_back(make_pair(C[i], i));
    sol=sol+Q.front().first*P[i]*1LL+S*(i-Q.front().second)*P[i]*1LL;
  }
  tu<<sol;
  return 0;
}