Cod sursa(job #393435)

Utilizator andreidragusAndrei Dragus andreidragus Data 9 februarie 2010 14:37:25
Problema Branza Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>
#include<vector>
#include<algorithm>
#include<map>
#include <set>
#include <iostream>

#define ll long long
#define N 10050

using namespace std;

int c[N];
int p[N];

int n, t, cost;
int s;
ll ans;

multiset<int> s1;
multiset<int>::iterator its[N];

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);

    cin >> n >> cost >> t;

    for (int i = 0; i < n; i++)
    {
	scanf("%d %d", &c[i], &p[i]);
    }

    for (int i = 0; i < n; i++)
    {
	its[i] = s1.insert(c[i] - s);

	if (s1.size() > t + 1)
	{
	    s1.erase(its[i-t-1]);
	}

	ans += (s + (*s1.begin())) * (ll) p[i];
	s += cost;
    }

    printf("%lld", ans);
    return 0;
}