SalmaHatem's blog

By SalmaHatem, history, 2 months ago,

Hello !

May anyone help me to solve this problem ?

Thank You.

• +12

 » 2 months ago, # |   0 Auto comment: topic has been updated by SalmaHatem (previous revision, new revision, compare).
 » 2 months 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) 
•  » » 2 months 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); } 
•  » » » 2 months ago, # ^ |   0 A good solution ,too Thank you !
•  » » 2 months ago, # ^ |   +3 Thank you !