132042025-01-07 02:11:04ubormaciFeladatkitűzéscpp17Accepted 100/10092ms9356 KiB
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <array>
#include <string>
#include <cstdio>
#include <iterator>
#include <unordered_set>
#include <cstdint>
using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

/*

notes:

int64_t
stoi(string s) -> string to int
to_string() -> int (or else) to string

vector declaration:
vector<ll> v(n, 0)
vector<vector<ll>> v(n, vector<ll>(n, 0));

{if statement} ? {truth value} : {false value}

set lower bound/upper bound:
 	// . . . m1 . . . d . . . . m2
    auto m1_it = b.lower_bound(d);
    advance(m1_it, -1);
    m1 = *m1_it;
	m2 = *b.upper_bound(d);

*/

typedef int64_t ll;

void solve() {
	ll n = 0;
	cin >> n;
	vector<ll> a(n, 0);
	vector<ll> b(n, 0);
	vector<ll> used(n, 0);
	ll minn = -1;
	for(ll i = 0; i < n; i++) {
		ll tmp;
		cin >> tmp;
		a[i] = tmp;
	}
	for(ll i = 0; i < n; i++) {
		ll tmp;
		if(i < n - 1) {
			cin >> tmp;
			b[i] = tmp;
		}
		ll currmaxx = a[i] + b[i];
		if(i > 0) {
			currmaxx += b[i-1];
		}
		if(minn == -1 || currmaxx < minn) {
			minn = currmaxx;
		}
	}

	// binaris kereses (yay)
	//cerr << "\n\nminn= " << minn;
	ll left = 0, right = minn;
	while(left < right) {
		//cerr << "\nleft=" << left;
		//cerr << "\nright=" << right;
		ll mid = left + (right - left + 1)/2;
		//cerr << "\nmid=" << mid;
		bool poss = true;

		ll prev = 0;
		for(ll i = 0; i < n; i++) {
			ll curr = a[i] + prev;
			if(curr >= mid) {
				prev = b[i];
				continue;
			}
			ll needed = mid - curr;
			if(needed > b[i]) {
				//cerr << "\nimpossible at " << i;
				poss = false;
				break;
			}else{
				prev = b[i] - needed;
			}
		}

		if(poss == true) {
			left = mid;
		}else{
			right = mid - 1;
		}
	}

	cout << left << "\n";
    
}

int main()
{
	std::ios_base::sync_with_stdio(false);

	ll tests = 0;
	cin >> tests;

	while(tests--)
	{
		solve();
	}

	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms500 KiB
subtask25/5
2Accepted70ms2612 KiB
3Accepted54ms7424 KiB
4Accepted59ms7476 KiB
subtask310/10
5Accepted52ms1076 KiB
6Accepted35ms1076 KiB
7Accepted34ms1076 KiB
8Accepted37ms3404 KiB
9Accepted37ms5684 KiB
subtask430/30
10Accepted52ms1076 KiB
11Accepted35ms1076 KiB
12Accepted34ms1076 KiB
13Accepted37ms3404 KiB
14Accepted37ms5684 KiB
15Accepted56ms1588 KiB
16Accepted57ms1584 KiB
17Accepted41ms6280 KiB
18Accepted46ms6848 KiB
subtask520/20
19Accepted74ms2620 KiB
20Accepted56ms7412 KiB
21Accepted59ms7476 KiB
subtask635/35
22Accepted1ms316 KiB
23Accepted70ms2612 KiB
24Accepted54ms7424 KiB
25Accepted59ms7476 KiB
26Accepted52ms1076 KiB
27Accepted35ms1076 KiB
28Accepted34ms1076 KiB
29Accepted37ms3404 KiB
30Accepted37ms5684 KiB
31Accepted56ms1588 KiB
32Accepted57ms1584 KiB
33Accepted41ms6280 KiB
34Accepted46ms6848 KiB
35Accepted74ms2620 KiB
36Accepted56ms7412 KiB
37Accepted59ms7476 KiB
38Accepted89ms4148 KiB
39Accepted92ms4148 KiB
40Accepted71ms8768 KiB
41Accepted75ms9356 KiB