Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Блог пользователя SalmaHatem_

Автор SalmaHatem_, история, 2 года назад, По-английски

Hello !

May anyone help me to solve this problem ?

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

Thank You.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
hint1
hint2
solution
python code
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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 <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);
    }
    
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thank you !