oj.uz

Submission #967218

# Submission time Handle Problem Language Result Execution time Memory
967218 2024-04-21T14:14:40 Z huutuan Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 5 ms 2652 KB 
#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;
      int d=__gcd(x, y);
      x/=d; y/=d;
   }
   bool operator<(const Fraction &b) const {
      return x*b.y>y*b.x;
   }
};

const int N=1e5+10;
int h, w, a[N], b[N], da[N], db[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) st.emplace(a[i]-a[i-1], 1, i);
   for (int i=2; i<=w; ++i) st.emplace(b[i]-b[i-1], 1, -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.emplace(b[*it]-b[*prev(it)], (*it)-(*prev(it)), -*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.emplace(a[*it]-a[*prev(it)], (*it)-(*prev(it)), *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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 2516 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 2 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 2516 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 2 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -