Submission #1335978

#TimeUsernameProblemLanguageResultExecution timeMemory
1335978gohchingjaykBikeparking (EGOI24_bikeparking)C++20
9 / 100
30 ms5088 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

using ll = long long;

#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;

constexpr int INF = 1e18 + 5;
constexpr int MAXN = 300'000 + 5;
constexpr int MOD = 1e9 + 7;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	
	int N; cin >> N;
	vector<int> X(N); for (int i = 0; i < N; ++i) cin >> X[i];
	vector<int> Y(N); for (int i = 0; i < N; ++i) cin >> Y[i];

	int sumY = 0; for (int i = 0; i < N; ++i) sumY += Y[i];
	int sumX = 0; for (int i = 0; i < N; ++i) sumX += X[i];
	
	int diff = sumX - sumY;
	for (int i = N-1; i >= 0; --i) {
		int sub = min(diff, X[i]);
		X[i] -= sub;
		diff -= sub;
	}
	
	int delta = 0;
	int ptr1 = N-2;
	for (int i = N-1; i >= 1; --i) {
		ptr1 = min(ptr1, i - 1);
		while (ptr1 >= 0) {
			if (Y[i] >= X[ptr1]) {
				Y[i] -= X[ptr1];
				delta += X[ptr1];
				X[ptr1] = 0;
				ptr1--;
			}
			else {
				X[ptr1] -= Y[i];
				delta += Y[i];
				break;
			}
		}
	}
	
	for (int i = 0; i < N; ++i) {
		int sub = min(X[i], Y[i]);
		X[i] -= sub;
		Y[i] -= sub;
	}
	
	for (int i = 0; i < N; ++i) delta -= Y[i];
	cout << delta;
}
#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...