Pagini recente » Cod sursa (job #803237) | Cod sursa (job #595404) | Cod sursa (job #215669) | Cod sursa (job #739011) | Cod sursa (job #68815)
Cod sursa(job #68815)
#include <stdio.h>
#define NMAX 100000
typedef struct deque
{
long long poz;
long long e;
};
deque d[NMAX+5];
inline long long min(long long a, long long b) { return (a < b) ? a : b; }
long long st, dr;
long long c[NMAX+5], p[NMAX+5];
long long n, t, s;
long long res;
int main()
{
long long i;
long long aux;
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
st = 1;
dr = 0;
scanf("%lld %lld %lld", &n, &s, &t);
for(i = 1; i <= n; ++i)
{
scanf("%ld%ld", c+i, p+i);
while(st <= dr && (long long)d[dr].e > (long long)c[i] + (long long)s*(n-i))
--dr;
d[++dr].poz = i;
d[dr].e = (long long)c[i] + (long long)s*(n-i);
res += (long long)((long long)d[st].e - (long long)s*(n-i)) * p[i];
if(i-t == d[st].poz)
++st;
}
printf("%lld\n", res);
return 0;
}