Submission #1179810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179810		tch1cherin	Sightseeing in Kyoto (JOI22_kyoto)	C++20	0 / 100	0 ms	328 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = (1 << 30) - 1;

struct fraction {
  int nom, denom;

  fraction() = default;

  fraction(int x) : nom(x), denom(1) {}

  fraction(int x, int y) : nom(x), denom(y) {}
};

int sign(fraction a) {
  if (a.nom == 0) {
    return 0;
  } else {
    bool neg = (a.nom < 0) ^ (a.denom < 0);
    return neg ? -1 : +1;
  }
}

bool operator<(fraction a, fraction b) {
  int sa = sign(a), sb = sign(b);
  if (sa != sb) {
    return sa < sb;
  }
  if (sa > 0) {
    return 1LL * abs(a.nom) * abs(b.denom) < 1LL * abs(a.denom) * abs(b.nom);
  } else {
    return 1LL * abs(a.nom) * abs(b.denom) > 1LL * abs(a.denom) * abs(b.nom);
  }
}

fraction intersect(int k1, int b1, int k2, int b2) {
  return fraction(b2 - b1, k1 - k2);
}

vector<int> convex_hull(vector<int> A) {
  vector<int> hull = {0};
  vector<fraction> points = {fraction(INF)};
  for (int i = 1; i < int(A.size()); i++) {
    while (!hull.empty() && !(intersect(i, A[i], hull.back(), A[hull.back()]) < points.back())) {
      points.pop_back();
      hull.pop_back();
    }
    points.push_back(intersect(i, A[i], hull.back(), A[hull.back()]));
    hull.push_back(i);
  }
  return hull;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int H, W;
  cin >> H >> W;
  vector<int> A(H), B(W);
  for (int &value : A) {
    cin >> value;
  }
  for (int &value : B) {
    cin >> value;
  }
  vector<int> A_hull = convex_hull(A);
  vector<int> B_hull = convex_hull(B);
  long long answer = 0;
  int i = 0, j = 0;
  int x = 0, y = 0;
  while (i + 1 < int(A_hull.size()) && j + 1 < int(B_hull.size())) {
    fraction P = intersect(A_hull[i], A[A_hull[i]], A_hull[i + 1], A[A_hull[i + 1]]);
    fraction Q = intersect(B_hull[i], B[B_hull[j]], B_hull[j + 1], B[B_hull[j + 1]]);
    if (!(P < Q)) {
      answer += 1LL * B[y] * (A_hull[i + 1] - x);
      x = A_hull[i + 1];
      ++i;
    } else {
      answer += 1LL * A[x] * (B_hull[j + 1] - y);
      y = B_hull[j + 1];
      ++j;
    }
  }
  while (i + 1 < int(A_hull.size())) {
    answer += 1LL * B[y] * (A_hull[i + 1] - x);
    x = A_hull[i + 1];
    ++i;
  }
  while (j + 1 < int(B_hull.size())) {
    answer += 1LL * A[x] * (B_hull[j + 1] - y);
    y = B_hull[j + 1];
    ++j;
  }
  cout << answer << "\n";
}

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