Cod sursa(job #781840)

Utilizator idomiralinIdomir Alin idomiralin Data 25 august 2012 11:21:51
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
# include <cstdio>
# include <algorithm>

using namespace std;

struct camp
{
       int t, p;
       }v[20005];

int cmp(camp x, camp y)
{
    return x.t < y.t;
}

int c, n;

int ssm(int pret)
{int j, s, max;

     s = 0; max = 0; 
     for (j = 1; j <= n; j++)
     {
         if (j > 1)
            s -= (v[j].t - v[j - 1].t) * c;
            
         if (s < 0) s = 0;
         
         if (v[j].p >= pret)
            s += pret;
            
         if (s - c > max) max = s - c;
         }
         
return max;
}

int main()
{int i, j, s, max;
    
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    
    scanf("%d %d",&n,&c);
    for (i = 1; i <= n; i++)
        scanf("%d %d",&v[i].t,&v[i].p);
        
    sort(v + 1, v + n + 1, cmp);
 
    max = 0;
    for (i = 1; i <= n; i++)
    {
        s = ssm(v[i].p);
        if (s > max)
                max = s;
                }        

    printf("%d",max); 
           
return 0;
}