Cod sursa(job #2927561)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 20 octombrie 2022 20:51:25
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 100003
#define MOD 1234567
using namespace std;

int n, cnst;
FILE* fin, * fout;


struct cumpar {
    int timp;
    int cost;
}v[NMAX];


bool cmp(cumpar a, cumpar b)
{
    if (a.timp == b.timp)
    {
        return a.cost < b.cost;
    }
    return a.timp < b.timp;
}

int main()
{
    fin = fopen("carnati.in","r");
    fout= fopen("carnati.out", "w");

    fscanf(fin,"%d %d", &n,&cnst);
    for (int i = 1; i <= n; i++)
    {
        fscanf(fin, "%d %d", &v[i].timp, &v[i].cost);
    }
    stable_sort(v + 1, v + n + 1, cmp);//sortez dupa timp
    
    int maximProf = INT_MIN;
    for (int i = 1; i <= n; i++)
    {
        //pentru fiecare valoare din vector imi setez pretul pentru hotdog cu v[i].cost :)
        int sum = 0, profit = INT_MIN;
        for (int j = 1; j <= n; j++)
        {
            sum -= (v[j].timp - v[j - 1].timp) * cnst;
            if (sum < 0)
            {
                sum = 0;
            }
            if (v[j].cost >= v[i].cost)
            {
                //ai facut o vanzare
                sum += v[i].cost;//cumpara la pretul stabilit
            }
            profit = max(profit, sum);
        }
        maximProf = max(profit-cnst, maximProf);//scad cu cnt pentru t0 cand incepe sa lucreze
    }
    fprintf(fout, "%d", maximProf);
    return 0;
}