Submission #1208173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208173		algoproclub	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	103 ms	5892 KiB

joi2019_ho_t4

// UUID: 42e19c60-a5a4-4828-87b4-f2d336494cfd
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
	ll n;
	cin >> n;

	ll ans = 0;

	vector<vector<ll>> cel(n + 1, vector<ll>(3, 0));
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= 2; j++){
			cel[i][j] = -1;
		}
	}

	for(ll i = 0; i < 2*n; i++){
		ll a, b;
		cin >> a >> b;

		if(a < 1){ // jobbra
			ans += (1 - a);
			a = 1;
		} else if(n < a){ // balra
			ans += (a - n);
			a = n;
		}

		if(b < 1){ // fel
			ans += (1 - b);
			b = 1;
		} else if(2 < b){ // le
			ans += (b - 2);
			b = 2;
		}

		cel[a][b]++;
	}
	
	for(ll i = 1; i <= n; i++){
		ans += abs(cel[i - 1][1]); // elozobol
		ans += abs(cel[i - 1][2]); // elozobol
		cel[i][1] += cel[i - 1][1];
		cel[i][2] += cel[i - 1][2];

		if(cel[i][1] < 0 && 0 < cel[i][2]){
			ll javit = min(-1*cel[i][1], cel[i][2]);
			cel[i][1] += javit;
			cel[i][2] -= javit;
			ans += javit;
		} else if(cel[i][2] < 0 && 0 < cel[i][1]){
			ll javit = min(-1*cel[i][2], cel[i][1]);
			cel[i][2] += javit;
			cel[i][1] -= javit;
			ans += javit;
		}
	}

	cout << ans << "\n";
}

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