Submission #898292

#	Time	Username	Problem	Language	Result	Execution time	Memory
898292		andrei_iorgulescu	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	37 ms	7240 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;
int a[5][100005];

int solve(int c)
{
    if (c == n + 1)
        return 0;
    int x = a[1][c],y = a[2][c];
    x--;
    y--;
    //cout << c << ' ' << x << ' ' << y << endl;
    if (x >= 0 and y >= 0)
    {
        a[1][c + 1] += x;
        a[2][c + 1] += y;
        //cout << c << ' ' << x + y << endl;
        return x + y + solve(c + 1);
    }
    if (x < 0 and y >= 0)
    {
        int md = min(y,-x);
        int cresc = md;
        x += md;
        y -= md;
        cresc += -x + y;
        a[1][c + 1] += x;
        a[2][c + 1] += y;
        //cout << c << ' ' << cresc << endl;
        return cresc + solve(c + 1);
    }
    else if (x >= 0 and y < 0)
    {
        int md = min(x,-y);
        int cresc = md;
        y += md;
        x -= md;
        cresc += -y + x;
        a[1][c + 1] += x;
        a[2][c + 1] += y;
        //cout << c << ' ' << cresc << endl;
        return cresc + solve(c + 1);
    }
    else
    {
        a[1][c + 1] += x;
        a[2][c + 1] += y;
        //cout << c << ' ' << -x - y << endl;
        return -x - y + solve(c + 1);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        int x,y;
        cin >> x >> y;
        if (x < 1)
        {
            ans += 1 - x;
            x = 1;
        }
        if (x > n)
        {
            ans += x - n;
            x = n;
        }
        if (y < 1)
        {
            ans += 1 - y;
            y = 1;
        }
        if (y > 2)
        {
            ans += y - 2;
            y = 2;
        }
        a[y][x]++;
    }
    ans += solve(1);
    cout << ans;
    return 0;
}

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