Cod sursa(job #2938445)

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

using namespace std;

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

const int NMAX = 3000;
const int TMAX = 2000;
const long long int VMAX = 2e15;

struct pers{
  int timp;
  int pret;
}v[NMAX+1];
int sclav[TMAX+1];

long long kadane(){
    long long int smax = -VMAX, sum = -VMAX;
    for(int j=1; j<=TMAX; j++){
        if(sum < 0)
            sum = 0;
        sum += sclav[j];
        smax = max(smax, sum);
    }
    return smax;
}

int main()
{
    int n, pret;
    f>>n>>pret;
    for(int i=1; i<=n; i++)
        f>>v[i].timp>>v[i].pret;
    
    long long smax = -VMAX;
    for(int i=1; i<=n; i++){
        fill(sclav+1, sclav+1+TMAX, -1*pret);
        for(int j=1; j<=n; j++)
            if(v[i].pret <= v[j].pret)
                sclav[v[j].timp] += v[i].pret;
        smax = max(smax, kadane());
                
    }
    g << smax;
    
    return 0;
}