Cod sursa(job #204107)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 21 august 2008 21:17:35
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
using namespace std;

#include <cstdio>
#include <algorithm>
#include <queue>

#define IN "branza.in"
#define OUT "branza.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<17

int N,T,S;
int C[N_MAX],P[N_MAX];
int B[N_MAX];
struct comp   
{  
    bool operator () (int x,int y)  
    { return (P[x] + (N-x)*S) > (P[y] + (N-y)*S); }  
};
priority_queue<int, vector<int>, comp> Q; 

void scan()
{
	char ch[1<<10];
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d%d\n", &N,&S,&T);
	FOR(i,1,N)
	{
		fgets(ch,1<<10,stdin);
		int k=-1;
		while(ch[++k]!=' ')
			P[i] = P[i] * 10 + ch[k] - '0';
		while(ch[++k]!='\n' && ch[k]!='\0')
			C[i] = C[i] * 10 + ch[k] - '0';
	}
}

void solve()
{
	int rez = 0;
	FOR(i,1,N)
	{
		Q.push(i);
		int nod = Q.top();
		while(i - nod > T)
		{
			Q.pop();
			nod = Q.top();
		}
		B[i] = (P[nod] + (N-nod)*S) - ((N - i) *S);
		rez += (int) B[i] * C[i];
		
	/*
		priority_queue<int, vector<int> ,comp> q(Q);
		while( !q.empty() )
		{
			nod = q.top();
			q.pop();
			printf("%d %d\n",nod,   (P[nod] + (N-nod)*S) - ((N - i) *S) );
		}
		printf("\n avem %d si min %d\n",rez,B[i]);
	*/	
	}	
	printf("%lld\n", rez);
}

int main()
{
	scan();
	solve();
	return 0;
}