Cod sursa(job #2938000)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 11 noiembrie 2022 15:26:24
Problema Carnati Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 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]);
    // if(mn == 1000000)
    //     mn = -10000;
    return mn;
}

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

    return 0;
}