Submission #629632

#	Time	Username	Problem	Language	Result	Execution time	Memory
629632		flappybird	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	444 ms	17360 KiB

kyoto

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 101010
#define MAXS 41
#define INF 1000000000000000001
#define MOD 1000000007
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
int B[MAX];
int pra[MAX], nea[MAX];
int prb[MAX], neb[MAX];
struct frac {
	int a, b, ind;
	frac(int a = 0, int b = 1, int ind = 0) :a(a), b(b), ind(ind) {}
};
bool operator<(frac f1, frac f2) { return (1ll * f1.a * f2.b < 1ll * f1.b * f2.a) || ((1ll * f1.a * f2.b == 1ll * f1.b * f2.a) && f1.ind < f2.ind); }
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int H, W;
	cin >> H >> W;
	int i;
	for (i = 1; i <= H; i++) cin >> A[i];
	for (i = 1; i <= W; i++) cin >> B[i];
	for (i = H; i > 1; i--) pra[i] = i - 1;
	for (i = W; i > 1; i--) prb[i] = i - 1;
	for (i = 1; i < H; i++) nea[i] = i + 1;
	for (i = 1; i < W; i++) neb[i] = i + 1;
	ll ans = 0;
	set<frac> sta, stb;
	for (i = 1; i < H; i++) sta.insert(frac(A[i + 1] - A[i], 1, i));
	for (i = 1; i < W; i++) stb.insert(frac(B[i + 1] - B[i], 1, i));
	int h, w;
	h = H;
	w = W;
	while (1) {
		if (sta.empty() || stb.empty()) {
			if (sta.empty()) ans += 1ll * (W - 1) * A[1];
			if (stb.empty()) ans += 1ll * (H - 1) * B[1];
			break;
		}
		if (*stb.rbegin() < *sta.rbegin()) {
			int k = (*sta.rbegin()).ind;
			int nk = nea[k];
			if (nk == H) {
				ans += 1ll * B[W] * (*sta.rbegin()).b;
				H = k;
				sta.erase(*sta.rbegin());
			}
			else {
				sta.erase(frac(A[nea[nk]] - A[nk], nea[nk] - nk, nk));
				sta.erase(*sta.rbegin());
				sta.emplace(frac(A[nea[nk]] - A[k], nea[nk] - k, k));
				pra[nea[nk]] = k;
				nea[k] = nea[nk];
			}
		}
		else {
			int k = (*stb.rbegin()).ind;
			int nk = neb[k];
			if (nk == W) {
				ans += 1ll * A[H] * (*stb.rbegin()).b;
				W = k;
				stb.erase(*stb.rbegin());
			}
			else {
				stb.erase(frac(B[neb[nk]] - B[nk], neb[nk] - nk, nk));
				stb.erase(*stb.rbegin());
				stb.emplace(frac(B[neb[nk]] - B[k], neb[nk] - k, k));
				prb[neb[nk]] = k;
				neb[k] = neb[nk];
			}
		}
	}
	cout << ans << ln;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:41:6: warning: variable 'h' set but not used [-Wunused-but-set-variable]
   41 |  int h, w;
      |      ^
kyoto.cpp:41:9: warning: variable 'w' set but not used [-Wunused-but-set-variable]
   41 |  int h, w;
      |         ^

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