oj.uz

Submission #920394

# Submission time Handle Problem Language Result Execution time Memory
920394 2024-02-02T14:07:19 Z borisAngelov Snowball (JOI21_ho_t2) C++17
33 / 100
 20 ms 5720 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int n, m;

long long a[maxn];
long long b[maxn];

long long maxDeltaL[maxn];
long long maxDeltaR[maxn];

long long maxLeft[maxn];
long long maxRight[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
    }

    long long currDelta = 0;

    for (int i = 1; i <= m; ++i)
    {
        currDelta += b[i];
        maxDeltaL[i] = min(maxDeltaL[i - 1], currDelta);
        maxDeltaR[i] = max(maxDeltaR[i - 1], currDelta);
    }

    maxLeft[1] = a[1] + maxDeltaL[m];
    maxRight[n] = a[n] + maxDeltaR[m];

    for (int i = 1; i <= n - 1; ++i)
    {
        // min time to intersect

        int l = 1;
        int r = m;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (a[i] + maxDeltaR[mid] <= a[i + 1] + maxDeltaL[mid])
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        maxRight[i] = a[i] + maxDeltaR[r];
        maxLeft[i + 1] = a[i + 1] + maxDeltaL[r];

        if (l <= m)
        {
            //decides who will get the snow

            if (b[l] < 0)
            {
                maxLeft[i + 1] = maxRight[i];
            }
            else
            {
                maxRight[i] = maxLeft[i + 1];
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << maxRight[i] - maxLeft[i] << "\n";
    }

    return 0;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2804 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 2 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2804 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 2 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Incorrect 20 ms 5720 KB Output isn't correct
21 Halted 0 ms 0 KB -