Cod sursa(job #2316620)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 12 ianuarie 2019 00:46:01
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
const int NR = 2001 ;
ifstream f ("carnati.in") ;
ofstream g ("carnati.out") ;
struct client
{
    int x , y ;
}v [ NR ];
bool cmp ( client a , client b )
{
    return a.x < b.x ;
}
int  best ;
int main ()
{
    int n , c ;
    f >> n >> c ;
    for ( int i = 1 ; i <= n ; ++ i )   f >> v [ i ].x >> v [ i ].y ;
    sort ( v + 1 , v + n + 1 , cmp ) ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        int maximleft = 0 , maximright = 0 , s = 0 ;
        for ( int j = i - 1 ; j >= 1 ; j -- )
        {
            if ( v [ j ].y >= v [ i ].y )
            s += v [ i ].y ;
            if ( s - ( v [ i ].x - v [ j ].x  )* c > maximleft )    maximleft = s - ( v [ i ].x - v [ j ].x  )* c ;
        }
        int sum = 0 ;
        for ( int j = i + 1 ; j <= n ; j ++ )
        {
            if ( v [ j ].y >= v [ i ].y )
            sum += v [ i ].y ;
            if ( sum - ( v [ j ].x - v [ i ].x  )* c > maximright )    maximright = sum - ( v [ j ].x - v [ i ].x  )* c ;
        }
        if ( maximleft + maximright + v [ i ].y - c > best ) best = maximleft + maximright + v [ i ].y - c ;
    }

    g << best ;
}