Pagini recente » Cod sursa (job #2894626) | Cod sursa (job #620672) | Cod sursa (job #2451797) | Cod sursa (job #43115) | Cod sursa (job #68375)
Cod sursa(job #68375)
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
#define FIN "branza.in"
#define FOUT "branza.out"
#define MAX 100020
#define tip_cifra char
#define CIFRE 20
long C[MAX], P[MAX];
long n, S, T;
class numar {
public:
tip_cifra a[CIFRE];
int nr;
void operator=(long long x) {
long old = nr; nr = 0;
while ( x ) {
a[++nr] = x%10;
x/=10;
}
while ( old>nr )
a[old--]=0;
}
void operator+=(numar x) {
long i,t=0;
for (i=1; i<=nr || i<=x.nr || t; ++i, t/=10)
a[i] = (t = (a[i]+=t+x.a[i])) % 10;
nr = i-1;
}
void operator+=(long long x) {
numar b;
b.nr = 0;
b = x;
*this += b;
}
bool operator<(numar x) {
if ( nr<x.nr )
return true;
if ( nr>x.nr )
return false;
// a[0] == x.a[0]
long i=nr;
while (i && a[i] == x.a[i])
--i;
return (a[i]<x.a[i]);
}
};
long A[MAX];
numar Sum;
class deque {
public:
pair<long,long> V[MAX];
long p, u;
long next(long &x) {
x++;
if ( x==MAX )
x = 0;
return x;
}
long prev(long &x) {
x--;
if ( x<0 )
x = MAX-1;
return x;
}
deque() {
p = u = 0;
}
void push(long x, long y) {
pair<long,long> tmp = make_pair(x,y);
if ( p==u && !p && !V[0].first ) {
V[0] = tmp;
return ;
}
if ( x<V[p].first )
V[prev(p)] = tmp;
else {
while ( x < V[u].first )
prev(u);
V[next(u)] = tmp;
}
}
void update(long i) {
if ( !i )
return ;
while ( i-V[p].second>T )
next(p);
}
pair <long,long> pop() {
return V[p];
}
void debug() {
long i;
fprintf(stderr, "---------------------------\n");
for (i=p; i!=u; next(i))
fprintf(stderr, "%ld %ld\n", V[i].first, V[i].second);
fprintf(stderr, "%ld %ld\n", V[i].first, V[i].second);
}
} D;
int main() {
long i;
freopen(FIN, "r", stdin);
scanf("%ld %ld %ld", &n, &S, &T);
for (i=0; i<n; ++i)
scanf("%ld %ld", C+i, P+i);
fclose(stdin);
for (i=0; i<n; ++i) {
D.update(i);
D.push(C[i]+(n-i)*S, i);
// D.debug();
A[i] = D.pop().first - (n-i)*S;
}
for (i=0; i<n; ++i) {
Sum += A[i]*P[i];
}
freopen(FOUT, "w", stdout);
for (i=Sum.nr; i; --i)
printf("%d", Sum.a[i]);
printf("\n");
/* for (i=0; i<n; ++i)
printf("%ld\n", A[i]);*/
fclose(stdout);
return 0;
}