Submission #779336

#	Time	Username	Problem	Language	Result	Execution time	Memory
779336		borisAngelov	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	43 ms	4912 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int n;

int cnt[3][maxn];

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

int main()
{
    fastIO();

    cin >> n;

    long long ans = 0;

    for (int i = 1; i <= 2 * n; ++i)
    {
        int x, y;
        cin >> y >> x;

        if (x <= 1)
        {
            ans += abs(1 - x);
            x = 1;
        }

        if (x >= 2)
        {
            ans += abs(x - 2);
            x = 2;
        }

        if (y <= 1)
        {
            ans += abs(1 - y);
            y = 1;
        }

        if (y >= n)
        {
            ans += abs(y - n);
            y = n;
        }

        ++cnt[x][y];
    }

    int sum1 = 0;
    int sum2 = 0;

    for (int i = 1; i <= n; ++i)
    {
        sum1 += cnt[1][i];
        sum2 += cnt[2][i];

        if (sum1 > i && sum2 < i)
        {
            int transfer = min(sum1 - i, i - sum2);
            ans += transfer;

            sum1 -= transfer;
            sum2 += transfer;
        }

        if (sum1 < i && sum2 > i)
        {
            int transfer = min(i - sum1, sum2 - i);
            ans += transfer;

            sum1 += transfer;
            sum2 -= transfer;
        }

        ans += abs(sum1 + sum2 - 2 * i);
    }

    cout << ans << endl;

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63