Cod sursa(job #2938086)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 11 noiembrie 2022 16:30:02
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

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

const int NMAX = 1e6;
const long long VMAX = 2e18;



struct om{
  int pret;
  int timp;
} v[NMAX+1];

bool comp(om x, om y){
    return x.timp < y.timp;
}

int main()
{
    int n, angajat;
    f >> n  >> angajat;
    long long smax = -VMAX;
    for(int i=1; i<=n; i++)
        f >> v[i].timp >> v[i].pret;
    sort(v, v+1+n, comp);
    long long sfinal = -VMAX;
    for(int i=0; i<=n; i++){
        int pretSet = v[i].pret;
        int st = 0;
        long long smax = -VMAX;
        long long sum = -VMAX;
        for(int j=1; j<=n; j++){
            if(pretSet <= v[j].pret){
                if(sum - (long long)angajat*(1 + v[j].timp - v[st].timp) < 0)
                    sum = 0, st = j;
                sum += pretSet;
                
            }
            smax = max(smax, sum - (long long)angajat*(1 + v[j].timp - v[st].timp));
        }
        sfinal = max(sfinal, smax);
    }
    g<<sfinal;

    return 0;
}