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>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define szz(r) (ll)r.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
struct line{
ll a,b,c,d;
bool operator<(const line &o)const{
return a*o.b<o.a*b;
}
};
const int mxn=1e5+5;
bool dla[mxn]{0},dlb[mxn]{0};
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int h,w;cin>>h>>w;
ll a[h+1],b[w+1];
int la[h+2],ra[h+2],lb[w+2],rb[w+2];
for(int i=1;i<=h;i++)cin>>a[i],la[i]=i-1,ra[i]=i+1;
for(int i=1;i<=w;i++)cin>>b[i],lb[i]=i-1,rb[i]=i+1;
priority_queue<line>qa,qb;
for(int i=2;i<=h;i++)qa.push({a[i]-a[i-1],1,i-1,i});
for(int i=2;i<=w;i++)qb.push({b[i]-b[i-1],1,i-1,i});
ll rs=0;int lsa=h,lsb=w;
while(!qa.empty()||!qb.empty()){
if(!qb.empty()&&(qa.empty()||qa.top()<qb.top())){
auto u=qb.top();qb.pop();
if(dlb[u.c]||dlb[u.d])continue;
//cout<<b[u.c]<<' '<<b[u.d]<<" B\n";
if(u.d==lsb){
rs+=u.b*a[lsa];
lsb-=u.b;
}dlb[u.d]=1;
rb[u.c]=rb[u.d];
lb[rb[u.d]]=u.c;
if(u.c!=0&&rb[u.d]!=w+1)qb.push({b[rb[u.d]]-b[u.c],rb[u.d]-u.c,u.c,rb[u.d]});
}
else {
auto u=qa.top();qa.pop();
if(dla[u.c]||dla[u.d])continue;
//cout<<a[u.c]<<' '<<a[u.d]<<" A\n";
if(u.d==lsa){
rs+=u.b*b[lsb];
lsa-=u.b;
}dla[u.d]=1;
ra[u.c]=ra[u.d];
la[ra[u.d]]=u.c;
if(u.c!=0&&ra[u.d]!=h+1)qa.push({a[ra[u.d]]-a[u.c],ra[u.d]-u.c,u.c,ra[u.d]});
}
}cout<<rs;
}
Compilation message (stderr)
kyoto.cpp: In function 'int main()':
kyoto.cpp:28:9: warning: variable 'la' set but not used [-Wunused-but-set-variable]
28 | int la[h+2],ra[h+2],lb[w+2],rb[w+2];
| ^~
kyoto.cpp:28:25: warning: variable 'lb' set but not used [-Wunused-but-set-variable]
28 | int la[h+2],ra[h+2],lb[w+2],rb[w+2];
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |