Cod sursa(job #307027)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 22 aprilie 2009 19:33:57
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
//#include<algorithm>
//using namespace std;
#include<stdio.h>

#define DIM 100001
//#define DIM 101

int n,s,t,sol[DIM];
long long rez;

struct branza{
    int c,p;};
branza a[DIM];

struct deque{
    int x,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;}