Pagini recente » Cod sursa (job #1746560) | Cod sursa (job #3041608) | Cod sursa (job #2817804) | Cod sursa (job #2103870) | Cod sursa (job #462012)
Cod sursa(job #462012)
#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;
}