Cod sursa(job #679936)

Utilizator vladstoickvladstoick vladstoick Data 13 februarie 2012 20:56:42
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("carnati.in");
ofstream out("carnati.out");
struct client
{
    int p,t;
};
client v[2001];
int n , m , i , j ,s , maxi,local;
bool comp(client a , client b)
{
    if(a.t<b.t)
        return 1;
    return 0;
}
int rezultat(int timp , client a , int costTimp , int pretCarnat)
{
    int consumTimp = - (    ( a.t - timp ) *costTimp   );//minus totul
    if(pretCarnat>a.p )
        return consumTimp;
    else
        return consumTimp+pretCarnat;
}

int main()
{
    in>>n>>m;
    for(i=1;i<=n;i++)
        in>>v[i].t>>v[i].p;
    int old=v[1].t-1;
    sort(v+1,v+1+n,comp);
    for(i=1;i<=n;i++)
    {
        s=0;
        old=v[1].t-1;
        for(j=1;j<=n;j++)
        {
            //calculare rezultat
            local = rezultat( old , v[j],m,v[i].p);
            //verificare
            if(s + local > 0 )
            {
                //adunare
                s=s + local;
                old=v[j].t;
                if(s>maxi)
                    maxi=s;
            }
            else
            {
                if(v[j].p>=v[i].p && v[i].p-m>0)
                {
                    s=v[i].p-m;
                    old=v[j].t;
                }
                else
                {
                    s=0;
                    old=v[j+1].t-1;
                }

            }
        }
    }
    out<<maxi-m;
}