Hello !
May anyone help me to solve this problem ?
https://atcoder.jp/contests/abc172/tasks/abc172_c?lang=en
Thank You.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Hello !
Thank You.
Name |
---|
create prefix sums on A and B arrays.
use binary search.
let'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.
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})$$$.
Thank you !