Submission #99276

#	Time	Username	Problem	Language	Result	Execution time	Memory
99276		imeimi2000	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	91 ms	4976 KiB

joi2019_ho_t4

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long llong;

int n;
int cnt[100001][2];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    llong ans = 0;
    for (int i = 0; i < n + 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;
        }
        else {
            ans += y - 2;
            y = 2;
        }
        ++cnt[x][y - 1];
    }
    int sum[2] = {};
    for (int i = 1; i <= n; ++i) {
        sum[0] += cnt[i][0] - 1;
        sum[1] += cnt[i][1] - 1;
        if ((llong)sum[0] * sum[1] < 0) {
            int go = min(abs(sum[0]), abs(sum[1]));
            ans += go;
            if (sum[0] < 0) {
                sum[0] += go;
                sum[1] -= go;
            }
            else {
                sum[0] -= go;
                sum[1] += go;
            }
        }
        ans += abs(sum[0]) + abs(sum[1]);
    }
    printf("%lld\n", ans);
    return 0;
}

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