Buonasera, ho bisogno di un aiuto per il problema problemsetting.
nel mio codice cerco di implementare una ricerca binaria dove vado a trovare il piu grande valore che soddisfi la condizione, tuttavia ottengo solo 60/ 100 per errore output. vi lascio qua il il link al problema e il codice, grazie.
(Training - Problem Setting).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve(vector<ll>A, vector<ll>B, int N, ll x){
for(int i = 0; i < N - 1; i++){
for(int j = 0; j < 2; j++){
ll togli = 0;
if(A[i + j] < x){
togli = x - A[i + j];
}
togli = min(togli, B[i]);
A[i + j] += togli;
B[i] -= togli;
}
}
for(int i = 0; i < N; i++){
if(A[i] < x) return false;
}
return true;
}
ll upBd(vector<ll>&A, vector<ll>&B, int N, int x){
ll l = 0, r = x;
while(l < r){
ll mid = (l + r) / 2;
if(solve(A, B, N, mid)){
l = mid + 1;
}else{
r = mid;
}
}
return l;
}
int main() {
// uncomment the two following lines if you want to read/write from files
// ifstream cin("input.txt");
// ofstream cout("output.txt");
int T;
cin >> T;
for (int test = 1; test <= T; ++test) {
int N;
cin >> N;
vector<ll> A(N);
ll p = 0;
for (int i = 0; i < N; ++i){
cin >> A[i];
}
vector<ll> B(N - 1);
for (int i = 0; i < N - 1; ++i){
cin >> B[i];
}
for(int i = 0; i < N; i++){
int cB = 0;
if(i == 0) cB = B[0];
else if(i == N - 1) cB = B[N - 2];
else cB = B[i] + B[i + 1];
p = max(p, A[i] + B[i]);
}
ll K = upBd(A, B, N, p);
K = max(K - 1, 0LL);
// INSERT YOUR CODE HERE
cout << K<< endl;
}
return 0;
}