Submission #1179776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179776		MongHwa	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	24 ms	2632 KiB

joi2019_ho_t4

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
using namespace std;

#define ll long long
#define INF 1e17
#define X first
#define Y second

ll stage[100005][3];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

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

        if(1 <= x && x <= n)
        {
            if(y > 1)
            {
                stage[x][2]++;
                ans += (y-2);
            }
            else
            {
                stage[x][1]++;
                ans += abs(1-y);
            }
        }
        else if(x < 1)
        {
            if(y > 1)
            {
                stage[1][2]++;
                ans += (abs(1-x)+abs(y-2));
            }
            else
            {
                stage[1][1]++;
                ans += (abs(1-x)+abs(y-1));
            }
        }
        else
        {
            if(y > 1)
            {
                stage[n][2]++;
                ans += (abs(n-x)+abs(y-2));
            }
            else
            {
                stage[n][1]++;
                ans += (abs(n-x)+abs(y-1));
            }
        }
    }

    ll val1 = 0, val2 = 0;
    for(int i = 1; i <= n; i++)
    {
        val1 += (stage[i][1]-1);
        val2 += (stage[i][2]-1);

        if(val1 > 0 && val2 < 0)
        {
            ll tmp = min(val1, -val2);
            ans += tmp;
            val1 -= tmp;
            val2 += tmp;
        }
        if(val1 < 0 && val2 > 0)
        {
            ll tmp = min(-val1, val2);
            ans += tmp;
            val1 += tmp;
            val2 -= tmp;
        }

        ans += (abs(val1)+abs(val2));
    }

    cout << ans << '\n';
}

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