Cod sursa(job #547305)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 6 martie 2011 11:03:16
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.42 kb
#include<fstream>
using namespace std;
long long n,t,S,v[100010],v1[100010],v3[100010],st,dr,s;
int main()
{ifstream q("branza.in");
ofstream w("branza.out");
q>>n>>S>>t;
for(int i=1;i<=n;++i)
  q>>v[i]>>v1[i];
st=1;
dr=0;
for(int i=1;i<=n;++i)
  {while(st<=dr&&v[i]<v[v3[dr]]+S*(i-v3[dr]))
      --dr;
  v3[++dr]=i;
  if(v3[st]==i-t-1)
   ++st;
  s=s+(v[v3[st]]+(i-v3[st])*S)*v1[i];}
w<<s<<"\n";
return 0;}