Submission #734704

#	Time	Username	Problem	Language	Result	Execution time	Memory
734704		stevancv	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	64 ms	4904 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 2e9 + 2;
int cnt[N][3];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    ll 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;
        }
        cnt[x][y] += 1;
    }
    ll u, d;
    u = d = 0;
    for (int i = 1; i <= n; i++) {
        u += cnt[i][1] - 1;
        d += cnt[i][2] - 1;
        if (u < 0 && d > 0) {
            ll x = min(-u, d);
            ans += x;
            u += x;
            d -= x;
        }
        if (u > 0 && d < 0) {
            ll x = min(u, -d);
            ans += x;
            u -= x;
            d += x;
        }
        ans += abs(u) + abs(d);
    }
    cout << ans << en;
    return 0;
}

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