Submission #967231

#	Time	Username	Problem	Language	Result	Execution time	Memory
967231		huutuan	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	540 ms	32344 KiB

kyoto

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct Fraction{
   int x, y, i;
   Fraction (int _x=0, int _y=1, int _i=0){
      x=_x, y=_y, i=_i;
      if (y<0) y*=-1, x*=-1;
   }
   bool operator<(const Fraction &b) const {
      return make_pair(x*b.y, i)>make_pair(b.x*y, b.i);
   }
};

const int N=1e5+10;
int h, w, a[N], b[N], da[N], db[N];
Fraction ca[N], cb[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> h >> w;
   for (int i=1; i<=h; ++i) cin >> a[i];
   for (int i=1; i<=w; ++i) cin >> b[i];
   set<Fraction> st;
   set<int> sta, stb;
   for (int i=1; i<=h; ++i) sta.insert(i);
   for (int i=1; i<=w; ++i) stb.insert(i);
   for (int i=2; i<=h; ++i) ca[i]=Fraction(a[i]-a[i-1], 1, i), st.insert(ca[i]);
   for (int i=2; i<=w; ++i) cb[i]=Fraction(b[i]-b[i-1], 1, -i), st.insert(cb[i]);
   int x=h, y=w;
   int ans=0;
   while ((x!=1 || y!=1) && st.size()){
      auto p=*st.begin(); st.erase(st.begin());
      if (p.i<0){
         p.i=-p.i;
         db[p.i]=1;
         stb.erase(p.i);
         auto it=stb.lower_bound(p.i);
         if (it!=stb.end()){
            st.erase(cb[*it]);
            cb[*it]=Fraction(b[*it]-b[*prev(it)], (*it)-(*prev(it)), -*it), st.insert(cb[*it]);
         }
         if (da[x] && db[y]){
            while (da[x]) --x, ans+=b[y];
         }
      }else{
         da[p.i]=1;
         sta.erase(p.i);
         auto it=sta.lower_bound(p.i);
         if (it!=sta.end()){
            st.erase(ca[*it]);
            ca[*it]=Fraction(a[*it]-a[*prev(it)], (*it)-(*prev(it)), *it), st.insert(ca[*it]);
         }
         if (da[x] && db[y]){
            while (db[y]) --y, ans+=a[x];
         }
      }
   }
   while (x!=1) --x, ans+=b[y];
   while (y!=1) --y, ans+=a[x];
   cout << ans << '\n';
   return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60