Cod sursa(job #679970)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 13 februarie 2012 21:59:44
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define ff first
#define ss second
using namespace std;

vector < pair<int,int> > v;
int n,C,best;

void citire() {
	
	int i,x,y;
	ifstream in("carnati.in");
	in>>n>>C;
	
	for(i=0;i<n;i++) {
		in>>x>>y;
		v.push_back(make_pair(x,y));
		}
	
	in.close();

}
void afis() {
	
	ofstream out("carnati.out");
	out<<best<<'\n';
	out.close();

}
int main() {
	
	int i,j,pret,S;
	
	citire();
	sort(v.begin(),v.end());

	for(i=0;i<n;i++) {
		
		pret=v[i].ss;
		S=0;
		
		for(j=1;j<n;j++) {
			S-=(v[j].ff-v[j-1].ff-1)*C;
			
			if(S<0)
				S=0;
			if(pret<=v[j].ss)
				S+=pret;
			S-=C;
			if(S>best)
				best=S;
			
			}
		}
	
	afis();

	return 0;
	
}