Pagini recente » Cod sursa (job #2600629) | Cod sursa (job #2952852) | Cod sursa (job #2238753) | Cod sursa (job #2600635) | Cod sursa (job #571318)
Cod sursa(job #571318)
#include <iostream>
#include <fstream>
using namespace std;
const char iname[] = "branza.in";
const char oname[] = "branza.out";
const int nmax = 100005;
ifstream fin(iname);
ofstream fout(oname);
long long dp[nmax], t, s, p, n, pret[nmax], C[nmax], dq[nmax], sol;
long long i, front, back;
int main()
{
fin >> n >> s >> t;
for(i = 1; i <= n; i ++)
fin >> C[i] >> pret[i];
front = 1, back = 0;
for(i = 1; i <= n; i ++)
{
if(i - t > dq[front])
++front;
while(C[i] <= C[dq[back]] + (i - dq[back]) * s && back > 0 && front <= back)
--back;
dq[++back] = i;
sol = sol + (C[dq[front]] + (i - dq[front]) * s) * pret[i];
}
fout << sol << "\n";
return 0;
}