SalmaHatem's blog

By SalmaHatem, history, 7 weeks ago, In English

Hello !

May anyone help me to solve this problem ?

https://atcoder.jp/contests/abc172/tasks/abc172_c?lang=en

Thank You.

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SalmaHatem (previous revision, new revision, compare).

»
7 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it
hint1
hint2
solution
python code
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 <cstdio>
    #include <vector>
    #include <algorithm>
    
    int main()
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        std::vector<int> 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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you !