Submission #784781

#	Time	Username	Problem	Language	Result	Execution time	Memory
784781		SanguineChameleon	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	23 ms	4972 KiB

kyoto

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct point {
	long long x, y;

	point(): x(0), y(0) {};

	point(long long _x, long long _y): x(_x), y(_y) {};
};

point operator-(point p1, point p2) {
	return point(p1.x - p2.x, p1.y - p2.y);
}

long long operator^(point p1, point p2) {
	return p1.x * p2.y - p1.y * p2.x;
}

const int maxN = 1e5 + 20;
int A[maxN];
int B[maxN];

bool ccw(point p1, point p2, point p3) {
	return ((p1 - p2) ^ (p3 - p2)) < 0;
}

vector<point> build(int A[], int N) {
	point L(1, A[1]);
	point R(N, A[N]);
	vector<point> hull = {L};
	for (int i = 2; i <= N; i++) {
		point cur(i, A[i]);
		if (i != N && !ccw(L, cur, R)) {
			continue;
		}
		while ((int)hull.size() >= 2 && !ccw(hull.end()[-2], hull.back(), cur)) {
			hull.pop_back();
		}
		hull.push_back(cur);
	}
	return hull;
}

void just_do_it() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	for (int i = 1; i <= M; i++) {
		cin >> B[i];
	}
	vector<point> hullA = build(A, N);
	vector<point> hullB = build(B, M);
	int szA = hullA.size();
	int szB = hullB.size();
	int ptA = 0;
	int ptB = 0;
	int cx = 1;
	int cy = 1;
	long long res = 0;
	while (ptA < szA - 1 || ptB < szB - 1) {
		if (ptA < szA - 1 && (ptB == szB - 1 || ((hullA[ptA + 1] - hullA[ptA]) ^ (hullB[ptB + 1] - hullB[ptB])) > 0)) {
			ptA++;
			res += (hullA[ptA].x - cx) * B[cy];
			cx = hullA[ptA].x;
		}
		else {
			ptB++;
			res += (hullB[ptB].x - cy) * A[cx];
			cy = hullB[ptB].x;
		}
	}
	cout << res;
}

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