Cod sursa(job #1148046)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 20 martie 2014 13:15:26
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
using namespace std;

ifstream f("carnati.in");
ofstream g("carnati.out");

struct client {
    int p, t;
}a[2001],pivot,aux;

int n,c;

int pozdivizare(int li, int lf)
{
    int i,j;
    pivot=a[li];
    i=li-1;
    j=lf+1;
    do
    {
        do {i++;} while (a[i].t<pivot.t);
        do {j--;} while (a[j].t>pivot.t);
        if(i<j)
        {
            aux=a[i];
            a[i]=a[j];
            a[j]=aux;
        }
    }while(i<j);
    return j;
}

void quicksort(int li, int lf)
{
    int m;
    if(li==lf) return;
    m=pozdivizare(li,lf);
    quicksort(li,m);
    quicksort(m+1,lf);
}


int main()
{
    int i,j,end,s,max=-1,best,ind,cod;
    f>>n>>c;
    for(i=1;i<=n;i++)
        f>>a[i].t>>a[i].p;
    quicksort(1,n);
    for(i=1;i<=n;i++){
        s=0;
        best=-1;
        end=1;
        for(j=1;j<=n;j++){
            if(s<0){
                s=0;
                end=j;

            }
            if(a[j].p >= a[i].p)
                s =s + a[i].p;
            if(end==j)
                s =s-c;
            else{
                //if(end==j-1)
                //    s=s+c;
                s =s - (a[j].t-a[j-1].t)*c;
            }
            if(s>best)
                best=s;
             //g<<s<<" ";
        }
        if(best>max){
            max=best;
            ind=i;
        }
        //g<<"\n";
    }
    g<<max<<"\n";
    return 0;
}