Cod sursa(job #462012)
| Utilizator | Data | 9 iunie 2010 15:37:43 | |
|---|---|---|---|
| Problema | Branza | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.51 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]]+(long long)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]]+(long long)t*(i-dq[st]))*y;
}
out<<nr<<"\n";
return 0;
}
