Submission #807540

#	Time	Username	Problem	Language	Result	Execution time	Memory
807540		dong_liu	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	21 ms	5444 KiB

kyoto

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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)

#define ar array
#define all(v) begin(v), end(v)
#define sz(v) static_cast<int>(v.size())
typedef vector<int> vi;
typedef long long ll;

struct Point {
  ll x, y;
  bool operator<(const Point& p) const {
    return x < p.x || (x == p.x && y < p.y);
  }
  bool operator==(const Point& p) const { return (x == p.x && y == p.y); }
  Point operator-(const Point& p) const { return {x - p.x, y - p.y}; }
  friend ll abs(const Point& a) { return a.x * a.x + a.y * a.y; }
  friend ll cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
  }
  friend ll cross(const Point& p, const Point& a, const Point& b) {
    return cross(a - p, b - p);
  }
};

vector<Point> getHull(vi a) {
  vector<Point> p;
  F0R(i, sz(a)) {
    Point now = {i, a[i]};
    while (sz(p) > 1 && cross(p[sz(p) - 2], now, p[sz(p) - 1]) >= 0)
      p.pop_back();
    p.push_back(now);
  }
  return p;
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin.exceptions(cin.failbit);
  int n, m;
  cin >> n >> m;
  vi a(n), b(m);
  F0R(i, n) cin >> a[i];
  F0R(j, m) cin >> b[j];
  auto pa = getHull(a), pb = getHull(b);
  int i = 0, j = 0;
  ll ans = 0;
  while (i + 1 < sz(pa) || j + 1 < sz(pb)) {
    bool c;
    if (i + 1 == sz(pa))
      c = 0;
    else if (j + 1 == sz(pb))
      c = 1;
    else
      c = (pa[i + 1].y - pa[i].y) * (pb[j + 1].x - pb[j].x) <=
          (pb[j + 1].y - pb[j].y) * (pa[i + 1].x - pa[i].x);
    if (c)
      ans += (pa[i + 1].x - pa[i].x) * pb[j].y, i++;
    else
      ans += (pb[j + 1].x - pb[j].x) * pa[i].y, j++;
  }
  cout << ans << endl;
}

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