제출 #1335836

#제출 시각아이디문제언어결과실행 시간메모리
1335836gelastropodBikeparking (EGOI24_bikeparking)C++20
0 / 100
584 ms1114112 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;

#define SIZE 1000000000

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, a, ans = 0, crnt = 0; cin >> N;
	vector<int> X, Y, pX = { 0 }, pY = { 0 }, cX, cY;
	for (int i = 0; i < N; i++) {
		cin >> a;
		X.push_back(a);
		pX.push_back(a);
	}
	for (int i = 0; i < N; i++) {
		cin >> a;
		Y.push_back(a);
		pY.push_back(a);
	}
	cX = X, cY = Y;
	int idx = 0;
	for (int i = 0; i < N; i++) {
		while (cY[i] > cX[idx]) {
			if (idx < i) ans += cX[idx];
			else if (idx > i) ans -= cX[idx];
			cY[i] -= cX[idx++];
		}
		if (idx < i) ans += cY[i];
		else if (idx > i) ans -= cY[i];
		cX[idx] -= cY[i];
	}
	for (int i = 1; i <= N; i++) pX[i] += pX[i - 1], pY[i] += pY[i - 1];
	vector<int> sums(SIZE + 10, 0);
	for (int i = 0; i < N; i++) {
		auto iter1 = upper_bound(pY.begin(), pY.end(), pX[i]);
		auto iter2 = upper_bound(pY.begin(), pY.end(), pX[i + 1]);
		if (iter1 - pY.begin() <= i + 1 && i != 0) sums[max(0, pY[i] - pX[i])]++, sums[max(0, pY[i + 1] - pX[i])]--;
		if (iter2 - pY.begin() <= i + 1) sums[max(0, pY[i] - pX[i + 1])]++, sums[max(0, pY[i + 1] - pX[i + 1])]--;
	}
	for (int i = 1; i < sums.size(); i++) sums[i] += sums[i - 1];
	crnt = ans;
	for (int i = 0; i < sums.size(); i++) {
		crnt += sums[i] - 1 - (i >= Y[0]);
		ans = max(ans, crnt);
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...