Pagini recente » Cod sursa (job #1478856) | Cod sursa (job #918708) | Cod sursa (job #2578397) | Cod sursa (job #100261) | Cod sursa (job #462003)
Cod sursa(job #462003)
#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 && v[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,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;
}