Submission #430124

#	Time	Username	Problem	Language	Result	Execution time	Memory
430124		maximath_1	Coin Collecting (JOI19_ho_t4)	C++11	100 / 100	82 ms	6452 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;

const int MX = 2e5 + 5;
#define ll long long

int n, x[MX], y[MX], cnt[MX][2];
ll ans = 0ll;

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n;
	for(int i = 0; i < 2 * n; i ++){
		cin >> x[i] >> y[i];

		if(x[i] < 1){
			ans += 1 - x[i];
			x[i] = 1;
		}
		if(x[i] > n){
			ans += x[i] - n;
			x[i] = n;
		}
		if(y[i] < 1){
			ans += 1 - y[i];
			y[i] = 1;
		}
		if(y[i] > 2){
			ans += y[i] - 2;
			y[i] = 2;
		}

		cnt[x[i] - 1][y[i] - 1] ++;
	}

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

		if(need0 > 0 && need1 < 0){
			int move = min(need0, -need1);
			ans += move;
			need0 -= move;
			need1 += move;
		}
		if(need1 > 0 && need0 < 0){
			int move = min(need1, -need0);
			ans += move;
			need1 -= move;
			need0 += move;
		}

		ans += abs(need0) + abs(need1);
	}

	cout << ans << endl;
	return 0;
}

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