Cod sursa(job #2938016)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 11 noiembrie 2022 15:34:42
Problema Carnati Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <iostream>
#include <queue>

using namespace std;

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

const int NMAX = 2e3;
const long long VMAX = 2e9;

long long v[NMAX+1];
int n, price;
queue<int> q;

long long minim(int i, int j){
    long long mn = VMAX+1;
    for(int y=i; y<=j; y++)
        if(v[y])
            mn = min(mn, v[y]);
    return mn;
}

int contor(int i, int j){
    int cnt = 0;
    for(int y=i; y<=j; y++)
        if(v[y])
            cnt ++;
    return cnt;
}

int main()
{
    
    f>>n>>price;
    for(int i=1; i<=n; i++){
        int ind, pr;
        f >> ind >> pr;
        v[ind] = pr;
    }
    
   
    long long smax = 20*-VMAX;
      
    for(int i=1; i <= NMAX; i++){
        
        q.push(i);
        if(v[i] and (long long)minim(q.front(), i)*contor(q.front(), i) < (long long)minim(q.front(), i-1)*(contor(q.front(), i)-1))
            v[i] = 0;
        
        while(!q.empty() and contor(q.front(), i) and (long long) minim(q.front(), i)*contor(q.front(), i) - (long long)(i - q.front() + 1)*price < 0){
            q.pop();
        }
        
        
        
      
        if(smax < (long long)minim(q.front(), q.back())*contor(q.front(), i) - (long long)(i - q.front() + 1)*price)
            smax = (long long)minim(q.front(), q.back())*contor(q.front(), i) - (long long)(i - q.front() + 1)*price;
        
    }    
    g << smax;

    return 0;
}