Pagini recente » Monitorul de evaluare | Cod sursa (job #2353251) | Cod sursa (job #1937066) | Cod sursa (job #1648230) | Cod sursa (job #2561942)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("skiline.in");
ofstream fout("skiline.out");
long long h[40005];
int l[40005];
int st[40005];
int dr[40005];
vector<int>s1;
vector<int>s2;
bool x;
int i,j,k,a,y,maximilian,aria;
int main()
{
cin>>a;
for (i=1;i<=a;i++){
cin>>h[i]>>l[i];
}
s1.push_back(h[1]);
st[1]=l[1];
for (i=2;i<=a;i++){
st[i]=l[i];
x=0;
while (x==0){
x=s1.empty();
if (x==0){
if (s1.back()>h[i]){
st[i]+=st[s1.back()];
s1.pop_back();
}}
s1.push_back(h[i]);
}
s2.push_back(h[a]);
}
dr[1]=l[a];
for (i=a-1;i>=1;i--){
dr[i]=l[i];
x=0;
while (x==0){
x=s2.empty();
if (x==0){
if (s2.back()>h[i]){
dr[i]+=dr[s2.back()];
s2.pop_back();
}}}
s2.push_back(h[i]);
}
for (i=1;i<=a;i++){
aria=(st[i]+dr[i]-l[i])*h[i];
if (aria>maximilian){
maximilian=aria;
}}
cout<<maximilian;
return 0;
}