Cod sursa(job #137457)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 17 februarie 2008 12:18:38
Problema Carnati Scor 70
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasa a 10-a Marime 0.88 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector < pair <int , int > > v;
vector < int > k;
long long max_p;
int c, i, n, m, a, b;
void solve(int x)
{
	int left = 0, right = 0;
	long long prof= 0;
	k.clear();
	for (int i = 1; i < n; ++ i)
		if (v[i].second >= x)
			k.push_back(v[i].first);
	prof = x -c;
	for (left = 1; left < k.size(); ++ left)
	{
		prof+=x;
		prof -= (k[left] - k[left-1])*c;
		if (prof < 0)
		{
			prof = x-c;
			right = left;
		}
		if (prof > max_p)
			max_p = prof;
	}
	
}
	
int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d %d", &n, &c);
	for (i = 1; i <= n; ++ i)
	{
		scanf("%d %d", &a, &b);
		v.push_back(make_pair(a,b));
	}
	sort(v.begin(), v.end());
	for (i = 0; i <n; ++ i)
	{
		solve(v[i].second);
	}
	printf("%lld\n", max_p);
	return 0;
}