Cod sursa(job #462010)
Utilizator | mihai995 mihai995 | Data | 9 iunie 2010 15:36:06 |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.49 kb |
#include <fstream>
using namespace std;
int v[1<<17],dq[1<<17],n,k,t,st=1,dr;
ifstream in("branza.in");
ofstream out("branza.out");
inline void s(int x)
{
if (st<=dr && dq[st]==x-k)
st++;
}
void d(int x)
{
while (st<=dr && v[dq[dr]]+t*(x-dq[dr])>=v[x])
dr--;
dq[++dr]=x;
}
int main()
{
int i,x,y;
long long nr=0;
in>>n>>t>>k;
for (i=1;i<=n;i++)
{
in>>x>>y;
v[i]=x;
s(i);
d(i);
nr+=(v[dq[st]]+t*(i-dq[st]))*y;
}
out<<nr<<"\n";
return 0;
}