Cod sursa(job #204087)

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

#include <cstdio>
#include <algorithm>
#include <map>

#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
#define ll long long

ll N,T,S;
ll C[N_MAX],P[N_MAX];
ll B[N_MAX];
multimap<ll, ll> M; 

void scan()
{
	char ch[1<<10];
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%lld%lld%lld\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';
		--k;
		while(ch[++k]!='\n' && ch[++k]!='\0')
			C[i] = C[i] * 10 + ch[k] - '0';
		B[i] = (ll) P[i];
	}
}

void solve()
{
	ll rez(0);
	FOR(i,1,N)
	{
		M.insert( pair<ll,ll> (P[i] + (N-i)*S , i ));
		
		multimap<ll,ll>::iterator it;
		it = M.begin();
		
		if(i - (it->second) > T )
		{
			M.erase(it);
			it = M.begin();
			
		}	
		B[i] = it->first - ( (N - i) *S);
		rez += (ll) B[i] * C[i];
	}	
	printf("%lld\n", rez);
}

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