제출 #547409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547409		skittles1412	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	30 ms	6504 KiB

kyoto

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

using C = complex<long>;

long ccw(const C& a, C b, C c) {
	b -= a;
	c -= a;
	return (c * conj(b)).imag();
}

long ccw(const pair<long, long>& a, const pair<long, long>& b, const pair<long, long>& c) {
	return ccw(C {a.first, a.second}, C {b.first, b.second}, C {c.first, c.second});
}

vector<pair<long, long>> convex(const vector<long>& arr) {
	vector<pair<long, long>> ans;
	for (int i = 0; i < sz(arr); i++) {
		while (sz(ans) >= 2 && ccw(ans[sz(ans) - 2], ans[sz(ans) - 1], {i, arr[i]}) < 0) {
			ans.pop_back();
		}
		ans.emplace_back(i, arr[i]);
	}
	return ans;
}

void solve() {
	dbg(ccw(C {0, 1}, C {1, 2}, C {2, 1}));
	dbg(sz(convex({1, 2, 1})));
	int n, m;
	cin >> n >> m;
	vector<long> ina(n), inb(m);
	for (auto& a : ina) {
		cin >> a;
	}
	for (auto& a : inb) {
		cin >> a;
	}
	vector<pair<long, long>> arra = convex(ina), arrb = convex(inb);
	n = sz(arra);
	m = sz(arrb);
	dbg(n, m);
	int i = 0, j = 0;
	long ans = 0;
	while (i + 1 < n || j + 1 < m) {
		bool a;
		if (i + 1 == n) {
			a = false;
		} else if (j + 1 == m) {
			a = true;
		} else {
			a = (arra[i + 1].second - arra[i].second) * (arrb[j + 1].first - arrb[j].first) <=
				(arrb[j + 1].second - arrb[j].second) * (arra[i + 1].first - arra[i].first);
		}
		dbg(a);
		if (a) {
			ans += (arra[i + 1].first - arra[i].first) * arrb[j].second;
			i++;
		} else {
			ans += (arrb[j + 1].first - arrb[j].first) * arra[i].second;
			j++;
		}
	}
	cout << ans << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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