Cod sursa(job #1776360)

Utilizator edicCiuculescu Eduard edic Data 11 octombrie 2016 10:47:31
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#include<algorithm>
using namespace std;
pair<int ,int> v[2001];
int c[2001];
int d[2001];
int com(int i,int cc)
{
    if(v[i].second>=cc)
        return cc;
    return 0;
}
int dt(int i,int t)
{
    return (v[i].first-v[i-1].first)*t;
}
int main()
{
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    int n,i,t;
    scanf("%d%d",&n,&t);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].first,&v[i].second);
        c[i]=v[i].second;
    }
    sort(v+1,v+n+1);
    sort(c+1,c+n+1);
    int mas=-200000004,h,cc,aux,aut;
    for(h=n;h>=1;h--)
    {
        cc=c[h];
        for(i=1;i<=n;i++)
        {
            aux=com(i,cc);
            aut=dt(i,t);
            if(aux>d[i-1]+aux-aut)
            {
                d[i]=aux;
            }
            else
            {
                d[i]=d[i-1]+aux-aut;
            }
            if(d[i]>mas)
            {
                mas=d[i];
            }
        }
    }
    printf("%d",mas-t);
    return 0;
}