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;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define LINF 1023456789123456789
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,ii> iii;
int h,w;
ll a[100005],b[100005];
priority_queue<iii,vector<iii>,greater<iii>> pqh,pqv;
set<int> s1,s2;
inline ll rd(){
ll x=0;
char ch=getchar_unlocked();
while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace
while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
x=(x<<3)+(x<<1)+(ch&15);
ch=getchar_unlocked();
}
return x;
}
int main(){
h=(int)rd(),w=(int)rd();
for(int i=1;i<=h;++i){
a[i]=rd();
s1.insert(i);
if(i>1)pqh.push({a[i-1]-a[i],{i-1,i}});
}
for(int i=1;i<=w;++i){
b[i]=rd();
s2.insert(i);
if(i>1)pqv.push({b[i-1]-b[i],{i-1,i}});
}
pqh.push({LINF,{-1,-1}});
pqv.push({LINF,{-1,-1}});
ll ans=0;
while(pqh.size()+pqv.size()>2){
if(pqh.top().fi<pqv.top().fi){
ii p=pqh.top().se;pqh.pop();
if(!s1.count(p.fi)||!s1.count(p.se))continue;//already removed adjacent thing
int l=p.fi,r=-1;
auto it=s1.find(p.se);
if(it!=--s1.end())r=*next(it);
s1.erase(it);
if(r!=-1){
pqh.push({(double)(a[l]-a[r])/(r-l),{l,r}});
}
else ans+=b[*(--s2.end())]*(p.se-p.fi);
}
else{
ii p=pqv.top().se;pqv.pop();
if(!s2.count(p.fi)||!s2.count(p.se))continue;//already removed adjacent thing
int l=p.fi,r=-1;
auto it=s2.find(p.se);
if(it!=--s2.end())r=*next(it);
s2.erase(it);
if(r!=-1){
pqv.push({(double)(b[l]-b[r])/(r-l),{l,r}});
}
else ans+=a[*(--s1.end())]*(p.se-p.fi);
}
}
pf("%lld\n",ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |