Pagini recente » Cod sursa (job #328547) | Cod sursa (job #2963521) | Cod sursa (job #260065) | Cod sursa (job #1873352) | Cod sursa (job #2938003)
#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 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;
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;
}
g << smax;
return 0;
}