Submission #1117261

#TimeUsernameProblemLanguageResultExecution timeMemory
1117261imarnSightseeing in Kyoto (JOI22_kyoto)C++14
100 / 100
117 ms17856 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...