Cod sursa(job #2129530)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 12 februarie 2018 21:26:33
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("carnati.in") ;
ofstream fout("carnati.out") ;

int n , k ;
pair<int,int> om[2001] ;

bool compar(pair<int,int> p1 , pair<int,int> p2 )
{
    return p1.first < p2.first ;
}

int main()
{
    int i , j , cost , best , inc , ct ;
    fin >> n >> k ;
    for ( i = 1 ; i <= n ; i++ )
        fin >> om[i].first >> om[i].second ;
    sort(om+1,om+n+1,compar) ;
    best = -0x3f3f3f3f ;
    for ( i = 1 ; i <= n ; i++ )
    {
        cost = om[i].second ;
        ct = 0;
        inc = 1 ;
        for ( j = 1 ; j <= n ; j++ )
        {
            if ( om[j].second >= cost )
                ct++ ;
            if ( cost*ct < (om[j].first-om[inc].first+1)*k )
            {
                inc = j+1;
                ct = 0 ;
            }
            else
            {
                if ( cost*ct - (om[j].first-om[inc].first+1)*k > best )
                {
                    best = cost*ct-(om[j].first-om[inc].first+1)*k ;
                }
            }
        }
    }
    if ( best < 0 )
        fout << "0" ;
    else
        fout << best ;
}