Pagini recente » Cod sursa (job #1042697) | Cod sursa (job #1333291) | Cod sursa (job #2572580) | Cod sursa (job #2367866) | Cod sursa (job #2930417)
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAX 2002
using namespace std;
pair<int, int> v[MAX],t[MAX];
int n,dp[MAX],c,ans;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
int main()
{
fin >> n >> c;
for(int i = 1; i <= n; i++){
fin >> v[i].first >> v[i].second;
}
sort(v+1, v+n+1);
for(int i = 1; i <= n; i++){
/// fixam p ca fiind v[i].second
int cnt = 0;
for(int j = 1; j <= n; j++){
if(v[j].second >= v[i].second){
t[++cnt] = {v[j].first, v[j].second};
}
}
dp[1] = v[i].second-c;
ans = max(ans, dp[1]);
for(int j = 2; j <= cnt; j++){
dp[j] = max( v[i].second-c, dp[j-1]+v[i].second-c*(t[j].first-t[j-1].first) );
ans = max(ans, dp[j]);
}
}
fout << ans;
return 0;
}