Pagini recente » Cod sursa (job #2143241) | Cod sursa (job #703472) | Cod sursa (job #669238) | Cod sursa (job #1936188) | Cod sursa (job #1151398)
#include<fstream>
#define NMAX 100010
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
struct branza
{
int pret, c;
}a[NMAX];
int n, T, p=1, u=1, d[NMAX];
long long best[NMAX], s;
void Citeste()
{
int i;
f>>n>>s>>T;
for (i=1; i<=n; ++i)
f>>a[i].pret>>a[i].c;
}
void Solve()
{
int i;
best[1]=a[1].c*a[1].pret; d[1]=1;
for (i=2; i<=n; ++i)
{
if (d[p]==i-T) ++p;
while(u>=p && a[d[u]].pret+(i-d[u])*s>=a[i].pret)
--u;
d[++u]=i;
best[i]=best[i-1]+(a[d[p]].pret+(i-d[p])*s)*a[i].c;
}
g<<best[n]<<"\n";
}
int main()
{
Citeste();
Solve();
f.close();
g.close();
return 0;
}