Pagini recente » Cod sursa (job #2660692) | Cod sursa (job #2920011) | Cod sursa (job #3217929) | Cod sursa (job #2635807) | Cod sursa (job #1586811)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2005;
int N,K;
long long sol,dp[nmax];
struct el{
int t,x;
}a[nmax];
inline bool cmp(const el &A,const el &B){
return A.t < B.t;
}
inline long long Ok(int D){
int i;
long long best = 0;
for(i = 1; i <= N; ++i){
if(a[i].x < D) {dp[i] = dp[i-1]-K*1LL*(a[i].t-a[i-1].t); continue;}
dp[i] = max(0,dp[i-1]+D-K*1LL*(a[i].t-a[i-1].t));
best = max(best,dp[i]);
}
memset(dp,0,sizeof(dp));
return best;
}
int main(){
int i;
freopen("carnati.in","r",stdin);
freopen("carnati.out","w",stdout);
scanf("%d %d\n",&N,&K);
for(int i = 1; i <= N; ++i)
scanf("%d %d\n",&a[i].t,&a[i].x);
sort(a+1,a+N+1,cmp);
for(i = 1; i <= N; ++i)
sol = max(sol,Ok(a[i].x));
printf("%lld\n",sol);
return 0;
}