Cod sursa(job #2474132)

Utilizator CharacterMeCharacter Me CharacterMe Data 14 octombrie 2019 19:12:17
Problema Carnati Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
#define time first
#define cost second
typedef long long ll;
typedef std::pair<ll, ll> pl;
ll n, i, j, k, sol, c;
pl list[2001];
bool check[1501];
void read();
void solve();
void write();
int main()
{
    freopen("carnati.in", "r", stdin);
    freopen("carnati.out", "w", stdout);
    read();
    solve();
    write();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void read(){
    scanf("%lld%lld", &n, &c);
    for(i=1; i<=n; ++i) scanf("%lld%lld", &list[i].time, &list[i].cost);
}
void solve(){
    for(i=1; i<=n; ++i) if(!check[list[i].cost]){
        check[list[i].cost]=true;
        ll maxsum=-c;
        if(list[1].cost>=list[i].cost) maxsum+=list[i].cost;
        sol=std::max(sol, maxsum);
        for(j=2; j<=n; ++j){
            maxsum-=(list[j].time-list[j-1].time)*c;
            ll now=-c;
            if(list[j].cost>=list[i].cost){now+=list[i].cost; maxsum+=list[i].cost;}
            maxsum=std::max(maxsum, now);
            sol=std::max(sol, maxsum);
        }
    }
}
void write(){
    printf("%lld", sol);
}