https://www.hackerrank.com/contests/university-codesprint-2/challenges/game-of-two-stacks

2つのstack$A, B$が与えられる．どちらのstackからも数字を取ってよい．取った数字の和が$x$より大きくなった時点で失格となる．失格にならずに取った数字の和の最大値を求める．

stackなので$A, B$どちらも上からのみ数字を取ることができる．$v[i] = $上から$i$番目まで取った時の数字の和とすれば，$v$は広義単調増加となる．片方を$i$番目まで取ると決め打ちすると，もう片方からは最大で$x - v[i]$まで取ることができ，これは二分探索で求めることができる．$n, m \leq 10 ^5$なので$O(n log n)$で間に合う．

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
	int g;
	cin >> g;

	vector<ll> a, b, A, B;
	rep(q, g) {
		int n, m; ll x;
		cin >> n >> m >> x;

		a.clear(); b.clear();
		a.resize(n); b.resize(m);
		rep(i, n) cin >> a[i];
		rep(i, m) cin >> b[i];

		A = a; B = b;
		rep(i, n - 1) A[i+1] += A[i];
		rep(i, m - 1) B[i+1] += B[i];

		int ans = 0;

		rep(i, n + 1) {
			ll res = (i ? A[i-1] : 0);
			
			if(res <= x) ans = max(ans, i);
			else continue;

			ll diff = x - res + 1;
			vector<ll>::iterator it = lower_bound(B.begin(), B.end(), diff);
			int id = it - B.begin();

			if(id == 0) continue;
			ans = max(ans, i + id);

		}

		cout << ans << endl;
	}

	return 0;
}