Submission #1208173

#TimeUsernameProblemLanguageResultExecution timeMemory
1208173algoproclubCoin Collecting (JOI19_ho_t4)C++20
100 / 100
103 ms5892 KiB
// 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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...