Pagini recente » Cod sursa (job #1638100) | Cod sursa (job #2780127) | Cod sursa (job #2894265) | Cod sursa (job #31168) | Cod sursa (job #100139)
Cod sursa(job #100139)
#include <cstdio>
#include <deque>
#define maxN 100001
using namespace std;
deque <long long> dq;
long long N;
long long S;
long long T;
long long C[maxN];
long long D[maxN];
long long M[maxN];
long long cost(long long i)
{
return
C[i] + (N-i) * S;
}
void baga_dq(long long val)
{
if(dq.empty() == true)
dq.push_front(val);
else
{
if(cost(dq.back()) < cost(val))
dq.push_back(val);
else
{
while(cost(dq.back()) > cost(val) && dq.empty() == false)
dq.pop_back();
dq.push_back(val);
}
}
}
int main()
{
freopen("branza.in", "rt", stdin);
freopen("branza.out", "wt", stdout);
scanf("%lld %lld %lld", &N, &S, &T);
int i, lim;
long long min;
for(i=1; i<=N; ++i)
scanf("%lld %lld", C+i, D+i);
M[1] = C[1];
baga_dq(1);
for(i=2; i<=N; ++i)
{
lim = 1 > i - T ? 1 : i - T;
while(dq.front() < lim)
dq.pop_front();
min = cost(dq.front());
if(C[i] < min - ((N-i) * S))
M[i] = C[i];
else
M[i] = min - ((N-i) * S);
baga_dq(i);
}
long long sol = 0;
for(i=1; i<=N; ++i)
sol += D[i] * M[i];
printf("%lld", sol);
fclose(stdin);
fclose(stdout);
return 0;
}