### SalmaHatem's blog

By SalmaHatem, history, 7 weeks ago,

Hello !

# May anyone help me to solve this problem ?

Thank You.

• +12

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by SalmaHatem (previous revision, new revision, compare).
 » 7 weeks ago, # | ← Rev. 3 →   +1 hint1create prefix sums on A and B arrays. hint2use binary search. solutionlet's choose array A arbitrary to loop over all of its prefix sums and firstly check if this prefix sum is less than or equal to k.let the current prefix sum of A is su ,Then calculate rem=k-su and find rem in the prefix sum array of B using binary search ,then update the answer for each sum in A. python codefrom bisect import * n, m, k = map(int, input().split()) a, b = [int(x) for x in input().split()], [int(x) for x in input().split()] cuma, cumb = [0], [0] for i in range(n): cuma.append(cuma[-1] + a[i]) for i in range(m): cumb.append(cumb[-1] + b[i]) ans = 0 for i in range(n + 1): if cuma[i] > k: break rem = k - cuma[i] ix = bisect_right(cumb, rem) - 1 ans = max(ans, ix + i) print(ans) 
•  » » 7 weeks ago, # ^ |   0 You can see that the more books you read on the desk A, the less books you will read on the desk B. So there's no need to use binary search, you can simply calculate the number of books on the dest B from the previous value.The time complexity: $O(n + m)$, a bit faster the binary search $O(n\log{m})$. #include #include #include int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); std::vector a(n + 1), b(m + 1); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= m; i++) scanf("%d", &b[i]); int ans = 0; long long suma = 0, sumb = 0; for (int i = 1; i <= m; i++) sumb += b[i]; for (int i = 0, j = m; i <= n; i++) { suma += a[i]; while (j > 0 && suma + sumb > k) { sumb -= b[j]; j--; } if (suma + sumb > k) break; ans = std::max(ans, i + j); } printf("%d\n", ans); } 
•  » » » 7 weeks ago, # ^ |   0 A good solution ,too Thank you !
•  » » 7 weeks ago, # ^ |   +3 Thank you !