Submission #623009

#	Time	Username	Problem	Language	Result	Execution time	Memory
623009		iomoon191	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	34 ms	3896 KiB

kyoto

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

#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define M 998244353

typedef pair<int, int> pi;
typedef vector<int> vi;
#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"

const int N = 500005;
const int inf = 3e18;

int h, w;
vector<pi> a, b;

int calc(pi x, pi y, pi z){
	int x1 = y.fi - x.fi;
	int x2 = z.fi - x.fi;
	int y1 = y.se - x.se;
	int y2 = z.se - x.se;
	return (1ll * x1 * y2) - (1ll * y1 * x2);
}

void solve(){
	cin >> h >> w;
	foru(i, 1, h){
		int o; cin >> o;
		while(sz(a) > 1 and calc(a[sz(a) - 2], a[sz(a) - 1], pi(i, o)) <= 0) a.pop_back();
		a.emplace_back(i, o);
	}
	foru(i, 1, w){
		int o; cin >> o;
		while(sz(b) > 1 and calc(b[sz(b) - 2], b[sz(b) - 1], pi(i, o)) <= 0) b.pop_back();
		b.emplace_back(i, o);
	}
	int dx = 0, dy = 0, res = 0;
	while(dx < sz(a) - 1 or dy < sz(b) - 1){
		bool ok = false;
		if(dx + 1 == sz(a)) ok = true;
		else if(dx < sz(a) - 1 and dy < sz(b) - 1){
			pi px = pi(a[dx + 1].fi - a[dx].fi, a[dx + 1].se - a[dx].se);
			pi py = pi(b[dy + 1].fi - b[dy].fi, b[dy + 1].se - b[dy].se);
			if(calc(pi(0, 0), py, px) >= 0)	
				ok = true;
		}
		if(ok){
			res += 1ll * (b[dy + 1].fi - b[dy].fi) * a[dx].se;
			dy++;
		}
		else{
			res += 1ll * (a[dx + 1].fi - a[dx].fi) * b[dy].se;
			dx++;
		}
	}
	cout << res;
} 

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1; // cin >> t;
	while(t--){
		solve();
	}
}

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