Submission #1166407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166407		badge881	Snowball (JOI21_ho_t2)	C++20	100 / 100	108 ms	14408 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int numMax = 200005;

signed main()
{
    int nbBoules, nbWinds;
    scanf("%lld%lld", &nbBoules, &nbWinds);

    vector<int> coord(numMax + 1),
        winds(numMax + 1),
        tabCumul(numMax + 1),
        precalcul1(numMax + 1, 0),
        precalcul2(numMax + 1, 0),
        answer(numMax + 1);
    vector<pair<int, int>> b(nbBoules + 1);

    for (int i = 0; i < nbBoules; i++)
        scanf("%lld", &coord[i + 1]);
    for (int i = 0; i < nbWinds; i++)
        scanf("%lld", &winds[i + 1]);

    tabCumul[0] = 0;
    precalcul1[0] = precalcul2[0] = 0;
    for (int j = 0; j < nbWinds; j++)
    {
        tabCumul[j + 1] = tabCumul[j] + winds[j + 1];
        precalcul1[j + 1] = max(precalcul1[j], tabCumul[j + 1]);
        precalcul2[j + 1] = max(precalcul2[j], -tabCumul[j + 1]);
    }

    answer[1] = precalcul2[nbWinds];
    answer[nbBoules] = precalcul1[nbWinds];
    auto check = [&precalcul1, &precalcul2](int k, int tmp) -> bool
    {
        return ((precalcul1[k] + precalcul2[k]) <= tmp);
    };
    for (int i = 1; i < nbBoules; i++)
    {
        int tmp = coord[i + 1] - coord[i];
        int left = 1, right = nbWinds, res = 0;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (check(mid, tmp))
                res = mid, left = mid + 1;
            else
                right = mid - 1;
        }
        if (res > 0)
            b[i].first = precalcul1[res], b[i].second = precalcul2[res];
        if (res < nbWinds)
        {
            int pre_l = b[i].first, pre_r = b[i].second;
            int cur = tmp - pre_l - pre_r;
            if (tabCumul[res + 1] > 0)
                b[i].first += cur;
            else
                b[i].second += cur;
        }
    }
    for (int i = 1; i <= nbBoules; i++)
    {
        if (i < nbBoules)
            answer[i] += b[i].first, answer[i + 1] += b[i].second;
        printf("%lld\n", answer[i]);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%lld%lld", &nbBoules, &nbWinds);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%lld", &coord[i + 1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%lld", &winds[i + 1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67