Pagini recente » Cod sursa (job #292687) | Cod sursa (job #500087) | Cod sursa (job #2093128) | Cod sursa (job #2039979) | Cod sursa (job #2938016)
#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;
}