Cod sursa(job #2307051)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 23 decembrie 2018 17:21:40
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <bits/stdc++.h>
#define M -100000000
using namespace std;

struct client{
	int t,p;
}C[2010];

int c,n,sol=M;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

bool cmp(client a,client b){return a.t<b.t;}

int DP(int ind){
	int ans=M,sum=0,g=0;
	for(int i=1;i<=n;i++){
		if(C[ind].p<=C[i].p)g=C[ind].p;
		else g=0;
		sum=max(sum-(C[i].t-C[i-1].t)*c+g,g-c);
		ans=max(ans,sum);
	}
	return ans;
}

int main(){
	fin>>n>>c;
	C[0].t=C[0].p=-10;
	for(int i=1;i<=n;i++){
		fin>>C[i].t>>C[i].p;
	}
	sort(C+1,C+n+1,cmp);
	for(int i=1;i<=n;i++){
		sol=max(sol,DP(i));
	}
	fout<<sol;
	return 0;
}