제출 #846535

#제출 시각아이디문제언어결과실행 시간메모리
84653542kangarooCoin Collecting (JOI19_ho_t4)C++17
100 / 100
40 ms11344 KiB
//
// Created by 42kangaroo on 07/09/2023.
//
#include "bits/stdc++.h"

using namespace std;

#define int long long

struct Po {
	int x, y;
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<Po> a(2 * n);
	for (int i = 0; i < 2 * n; ++i) {
		cin >> a[i].x >> a[i].y;
		a[i].x--;
		a[i].y--;
	}
	int ans = 0;
	// move them into the box, make vector with number at each position
	vector<array<int, 2>> num(n, {0, 0});
	for (auto p: a) {
		if (p.x < 0) {
			ans += - p.x;
			p.x = 0;
		}
		if (p.x >= n) {
			ans += p.x - n + 1;
			p.x = n - 1;
		}
		if (p.y < 0) {
			ans += -p.y;
			p.y = 0;
		}
		if (p.y > 1) {
			ans += p.y - 1;
			p.y = 1;
		}
		num[p.x][p.y]++;
	}
	// At each pos, calculate how many go over boundary for up and down
	vector<array<int, 2>> dp(n + 1, {0, 0});
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			dp[i + 1][j] = dp[i][j] + num[i][j] - 1;
		}
		// if sum is > 0 and one is < 0, take one up
		for (int j = 0; j < 2; ++j) {
			if (dp[i + 1][j] < 0 && dp[i + 1][1 - j] > 0) {
				int mi = min(-dp[i + 1][j], dp[i + 1][1 - j]);
				ans += mi;
				dp[i + 1][j] += mi;
				dp[i + 1][1 -j] -= mi;
			}
		}
		ans += abs(dp[i + 1][0]) + abs(dp[i + 1][1]);
	}
	cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...