132042025-01-07 02:11:04ubormaciFeladatkitűzéscpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms500 KiB
subtask25/5
2Elfogadva70ms2612 KiB
3Elfogadva54ms7424 KiB
4Elfogadva59ms7476 KiB
subtask310/10
5Elfogadva52ms1076 KiB
6Elfogadva35ms1076 KiB
7Elfogadva34ms1076 KiB
8Elfogadva37ms3404 KiB
9Elfogadva37ms5684 KiB
subtask430/30
10Elfogadva52ms1076 KiB
11Elfogadva35ms1076 KiB
12Elfogadva34ms1076 KiB
13Elfogadva37ms3404 KiB
14Elfogadva37ms5684 KiB
15Elfogadva56ms1588 KiB
16Elfogadva57ms1584 KiB
17Elfogadva41ms6280 KiB
18Elfogadva46ms6848 KiB
subtask520/20
19Elfogadva74ms2620 KiB
20Elfogadva56ms7412 KiB
21Elfogadva59ms7476 KiB
subtask635/35
22Elfogadva1ms316 KiB
23Elfogadva70ms2612 KiB
24Elfogadva54ms7424 KiB
25Elfogadva59ms7476 KiB
26Elfogadva52ms1076 KiB
27Elfogadva35ms1076 KiB
28Elfogadva34ms1076 KiB
29Elfogadva37ms3404 KiB
30Elfogadva37ms5684 KiB
31Elfogadva56ms1588 KiB
32Elfogadva57ms1584 KiB
33Elfogadva41ms6280 KiB
34Elfogadva46ms6848 KiB
35Elfogadva74ms2620 KiB
36Elfogadva56ms7412 KiB
37Elfogadva59ms7476 KiB
38Elfogadva89ms4148 KiB
39Elfogadva92ms4148 KiB
40Elfogadva71ms8768 KiB
41Elfogadva75ms9356 KiB