Submission #523440

#	Time	Username	Problem	Language	Result	Execution time	Memory
523440		Monarchuwu	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	70 ms	5700 KiB

joi2019_ho_t4

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

const int N = 1e5 + 9;
int n, cnt[4][N];

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    ll sum(0);
    for (int i = 1, x, y; i <= n * 2; ++i) {
        cin >> x >> y;
        if (x < 1) sum += 1 - x, x = 1;
        if (n < x) sum += x - n, x = n;
        if (y < 1) sum += 1 - y, y = 1;
        if (2 < y) sum += y - 2, y = 2;
        ++cnt[y][x];
    }

    for (int i = 1; i <= n; ++i) {
        --cnt[1][i], --cnt[2][i];

        if (cnt[1][i] > 0 && cnt[2][i] < 0) {
            int mi = min(cnt[1][i], -cnt[2][i]);
            cnt[1][i] -= mi;
            cnt[2][i] += mi;
            sum += mi;
        }
        else if (cnt[1][i] < 0 && cnt[2][i] > 0) {
            int mi = min(-cnt[1][i], cnt[2][i]);
            cnt[1][i] += mi;
            cnt[2][i] -= mi;
            sum += mi;
        }

        cnt[1][i + 1] += cnt[1][i];
        sum += abs(cnt[1][i]);

        cnt[2][i + 1] += cnt[2][i];
        sum += abs(cnt[2][i]);
    }
    cout << sum << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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