This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct human
{
int a,b;
human(){}
human(int _a,int _b)
{
a=_a;
b=_b;
}
};
int n,maxx;
human h[200001];
bool cmp(human h1,human h2)
{
return h1.a<h2.a;
}
void read()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>h[i].a>>h[i].b;
maxx=max(maxx,h[i].b);
}
sort(h+1,h+n+1,cmp);
}
struct line
{
int a,b;
line(){}
line(int _a,int _b)
{
a=_a;
b=_b;
}
int value(int x)
{
return a*x+b;
}
};
int sq;
vector<line> v[200001];
int query(int b,int x)
{
if(v[b].size()==0)return 1e9;
if(v[b].size()==1)return v[b][0].value(x);
int ans=0;
int l=0,r=v[b].size()-2;
while(l<=r)
{
int m=(l+r)/2;
if(v[b][m].value(x)>v[b][m+1].value(x))
{
ans=max(ans,v[b][m].value(x));
r=m-1;
}
else
{
ans=max(ans,v[b][m+1].value(x));
l=m+2;
}
}
return ans;
}
double intersect(line l1,line l2)
{
return (double)(l2.b-l1.b)/(double)(l1.a-l2.a);
}
void add_to(int b,line l)
{
while(v[b].size()>=2&&intersect(v[b][v[b].size()-1],l)<intersect(v[b][v[b].size()-2],l))v[b].pop_back();
v[b].push_back(l);
}
int add[200001];
int cnt[200001];
void solve()
{
int ans=0;
sq=sqrt(maxx);
int k=maxx/sq;
if(maxx%sq)k++;
for(int i=1;i<=n;i++)
{
cnt[h[i].b]++;
int b=h[i].b/sq;
if(h[i].b%sq)b++;
add[b]++;
vector<line> in;
int till=0;
for(int j=min(maxx,b*sq);j>=(b-1)*sq+1;j--)
{
till+=cnt[j];
in.push_back({j,till*j});
}
for(int j=in.size()-1;j>=0;j--)
add_to(b,in[j]);
till=0;
for(int j=k;j>=1;j--)
{
ans=max(ans,query(j,till));
till+=add[j];
}
}
cout<<ans<<endl;
}
int main()
{
read();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |