Submission #561568

#	Time	Username	Problem	Language	Result	Execution time	Memory
561568		8e7	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	36 ms	5576 KiB

kyoto

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<ll, ll>
#define x first
#define y second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
pii vec(pii p, pii q){return {q.x - p.x, q.y - p.y};}
ll cross(pii p, pii q){return p.x * q.y - p.y * q.x;}

ll a[maxn], b[maxn];
int main() {
	io
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < n;i++) cin >> a[i];	
	for (int i = 0;i < m;i++) cin >> b[i];
	vector<pii> hl, hr;
	auto build_hull = [&] (int N, ll arr[], vector<pii> &v) {
		for (int i = 0;i < N;i++) {
			pii p = {i, arr[i]};
			while (v.size() > 1) {
				pii p1 = v[v.size() - 2], p2 = v.back();
				if (cross(vec(p2, p), vec(p2, p1)) <= 0) {
					v.pop_back();
				} else {
					break;
				}
			}
			v.push_back(p);
		}
	};
	build_hull(n, a, hl);
	build_hull(m, b, hr);
	ll ans = 0;	
	while (hl.size() > 1 || hr.size() > 1) {
		if (hl.size() == 1) {
			ans += hr.back().x * a[0];
			break;
		} else if (hr.size() == 1) {
			ans += hl.back().x * b[0];
			break;
		} else {
			ll ai = hl[hl.size()-2].y, aj = hl.back().y, bi = hr[hr.size()-2].y, bj = hr.back().y;
			ll X = hl.back().x - hl[hl.size()-2].x, Y = hr.back().x - hr[hr.size()-2].x;
			if ((bj - bi) * X < (aj - ai) * Y) {
				ans += bj * X;
				hl.pop_back();
			} else {
				ans += aj * Y;	
				hr.pop_back();
			}
		}
	}
	cout << ans << "\n";
}

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