Submission #873120

#	Time	Username	Problem	Language	Result	Execution time	Memory
873120		hct_2so1	Coin Collecting (JOI19_ho_t4)	C++17	37 / 100	20 ms	3928 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))

template <class X, class Y>
    bool minimize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 6e5;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 2e18;
const double eps = 1e-1;

int n, c[3][N];
pair<int, int> a[N];

void Input(void)
{
    cin >> n;
    for (int i = 1; i <= 2 * n; i ++) cin >> a[i].S >> a[i].F;
}

void solve(void)
{
    ll ans = 0;
    for (int i = 1; i <= 2 * n; i ++)
    {
        if (a[i].F < 1) ans += 1 - a[i].F, a[i].F = 1;
        if (a[i].F > 2) ans += a[i].F - 2, a[i].F = 2;
        if (a[i].S < 1) ans += 1 - a[i].S, a[i].S = 1;
        if (a[i].S > n) ans += a[i].S - n, a[i].S = n;
        c[a[i].F][a[i].S] ++;
    }
    int row[] = {0, 0, 0};
    for (int i = 1; i <= n; i ++)
    {
        c[1][i] --, c[2][i] --;
        row[1] += c[1][i];
        row[2] += c[2][i];
        if (row[1] < 0 && row[2] > 0)
        {
            int k = min(-row[1], row[2]);
            ans += k;
            row[1] += k;
            row[2] -= k;
        }
        else
            if (row[1] > 0 && row[2] < 0)
            {
                int k = min(row[1], -row[2]);
                ans += k;
                row[1] -= k;
                row[2] += k;
            }
        ans += abs(row[1]) + abs(row[2]);
    }
    cout << ans;
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("CLASSROOM.inp", "r", stdin);
//    freopen("CLASSROOM.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test --)
    {
        Input();
        solve();
    }
    return 0;
}

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