Cod sursa(job #1766337)

Utilizator giotoPopescu Ioan gioto Data 27 septembrie 2016 21:00:42
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#include <algorithm>
#define NMAX 2001
#define f first
#define s second
using namespace std;

int n,h,a[NMAX],b[NMAX],d[NMAX];
pair<int, int>v[NMAX];
int main()
{
    freopen("carnati.in", "r", stdin);
    freopen("carnati.out", "w", stdout);
    scanf("%d%d", &n, &h);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&v[i].f,&v[i].s);
    sort(v+1,v+n+1);
    int sol=0;
    a[0]=-10;b[0]=-10;
    for(int i=1;i<=n;++i)
        a[i]=v[i].f,b[i]=v[i].s;
    for(int j=1;j<=n;++j){
        for(int i=1;i<=n;++i){
            int g=b[j];
            if(b[i]<g) g=0;
            d[i]=max(d[i-1]-(a[i]-a[i-1])*h+g,g-h);
            if(sol<d[i]) sol=d[i];
        }
    }printf("%d", sol);
    return 0;
}