Submission #1336012

#TimeUsernameProblemLanguageResultExecution timeMemory
1336012gohchingjaykBikeparking (EGOI24_bikeparking)C++20
40 / 100
1095 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 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];
				Y[i] = 0;
				break;
			}
		}
	}
	*/

	for (int d = 1; d < N; ++d) {
		for (int i = N-1; i >= d; --i) {
			int ptr1 = i-d;
			if (Y[i] >= X[ptr1]) {
				Y[i] -= X[ptr1];
				delta += X[ptr1];
				X[ptr1] = 0;
			}
			else {
				X[ptr1] -= Y[i];
				delta += Y[i];
				Y[i] = 0;
			}

		}
	}

	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...