Submission #1207150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207150		siewjh	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	17 ms	6588 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ld inf = 1e18;
struct line{
	ll m, c;
};
struct hull{
	vector<line> v;
	ld poi(line a, line b){
		return (ld)(b.c - a.c) / (a.m - b.m);
	}
	void push(line a){
		while (v.size() >= 2 && poi(a, v.back()) < poi(v.back(), v[v.size() - 2])) v.pop_back();
		v.push_back(a);
	}
	ld getbp(){
		return (v.size() >= 2 ? poi(v.back(), v[v.size() - 2]) : -inf);
	}
};
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int rows, cols; cin >> rows >> cols;
	vector<ll> rv(rows), cv(cols);
	for (int i = 0; i < rows; i++) cin >> rv[i];
	for (int i = 0; i < cols; i++) cin >> cv[i];
	hull rh, ch;
	for (int i = rows - 1; i >= 0; i--) rh.push({i, rv[i]});
	for (int i = cols - 1; i >= 0; i--) ch.push({i, cv[i]});
	ll ans = 0, r = 0, c = 0;
	while (r < rows - 1 || c < cols - 1){
		if (rh.getbp() > ch.getbp()){
			rh.v.pop_back();
			ll nr = rh.v.back().m;
			ans += (nr - r) * cv[c];
			r = nr;
		}
		else{
			ch.v.pop_back();
			ll nc = ch.v.back().m;
			ans += (nc - c) * rv[r];
			c = nc;
		}
	}
	cout << ans;
}

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