Submission #898292

#TimeUsernameProblemLanguageResultExecution timeMemory
898292andrei_iorgulescuCoin Collecting (JOI19_ho_t4)C++14
100 / 100
37 ms7240 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...