Pagini recente » Utilizatori inregistrati la Algoritmiada 2013 - Runda 1, Clasele 11-12 | Istoria paginii runda/dotcom2012-runda2/clasament | Sedinta 2008-03-14 | Cod sursa (job #2588891) | Cod sursa (job #307029)
Cod sursa(job #307029)
#include<algorithm>
using namespace std;
#define DIM 100001
int n,s,t;
long long rez,sol[DIM];
struct branza{
int c,p;};
branza a[DIM];
struct deque{
int x;
long long val;};
deque dq[DIM];
void solve(){
int i,st,dr;
scanf("%d%d%d",&n,&s,&t);
for(i=1; i<=n; ++i)
scanf("%d%d",&a[i].c,&a[i].p);
st=1;
dr=0;
for(i=1; i<=n; ++i){
for(; st<=dr&&a[i].c+(n-i)*s<dq[dr].val; --dr);
dq[++dr].val=a[i].c+(n-i)*s;
dq[dr].x=i;
if(i-dq[st].x>t)
++st;
rez+=(sol[i]=dq[st].val-(n-i)*s)*a[i].p;}
printf("%lld",rez);}
int main(){
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
solve();
return 0;}