Cod sursa(job #1356059)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 23 februarie 2015 09:54:30
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream>
#include<algorithm>
#define t first
#define p second
using namespace std;
int n, i, j, maxim, x, pr, c;
int a[2001];
pair<int, int> v[2001];
ifstream fin("carnati.in");
ofstream fout("carnati.out");
int main(){
	fin>> n >> c;
	for(i = 1; i <= n; i++){
		fin>> v[i].t >> v[i].p;
	}
	sort(v + 1, v + n + 1);
	maxim = -1000000;
	for(j = 1; j <= n; j++){
		x = v[j].p;
		if(v[1].p >= x){
			pr = x;
		}
		else{
			pr = 0;
		}
		a[1] = pr - c;
		for(i = 2; i <= n; i++){
			if(v[i].p >= x){
				pr = x;
			}
			else{
				pr = 0;
			}
			a[i] = max(pr - c, a[i-1] + pr - (v[i].t - v[i-1].t) * c);
		}
		for(i = 1; i <= n; i++){
			maxim = max(maxim, a[i]);
		}
	}
	fout<< maxim <<"\n";
	return 0;
}