oj.uz

Submission #629631

# Submission time Handle Problem Language Result Execution time Memory
629631 2022-08-14T19:39:28 Z flappybird Sightseeing in Kyoto (JOI22_kyoto) C++17
10 / 100
 5 ms 1140 KB 
#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 50505
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 328 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Runtime error 5 ms 1140 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 328 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Runtime error 5 ms 1140 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -