Submission #1216186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216186		JooDdae	Sightseeing in Kyoto (JOI22_kyoto)	C++20	30 / 100	11 ms	1608 KiB

kyoto

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

int ccw(array<ll, 2> a, array<ll, 2> b, array<ll, 2> c) {
	return a[0]*b[1]+b[0]*c[1]+c[0]*a[1] - (a[1]*b[0]+b[1]*c[0]+c[1]*a[0]);
}

vector<array<ll, 2>> solve(vector<int> a) {
	vector<array<ll, 2>> re;
	for(int i=0;i<a.size();i++) {
		while(re.size() > 1 && ccw(re.rbegin()[1], re.back(), {i, a[i]}) <= 0) re.pop_back();
		re.push_back({i, a[i]});
	}
	return re;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m;
	vector<int> a(n), b(m);
	for(auto &x : a) cin >> x;
	for(auto &x : b) cin >> x;
	auto L = solve(a), R = solve(b);

	ll ans = 0;
	while(L.size() > 1 || R.size() > 1) {
		if(R.size() == 1 || (L.size() > 1 && (R.back()[1]-R.rbegin()[1][1])*(L.back()[0]-L.rbegin()[1][0]) <= (L.back()[1]-L.rbegin()[1][1])*(R.back()[0]-R.rbegin()[1][0]))) {
			auto k = L.back(); L.pop_back();
			ans += R.back()[1] * (k[0] - L.back()[0]);
		} else {
			auto k = R.back(); R.pop_back();
			ans += L.back()[1] * (k[0] - R.back()[0]);
		}
	}
	cout << ans;
}

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