Submission #846535

#	Time	Username	Problem	Language	Result	Execution time	Memory
846535		42kangaroo	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	40 ms	11344 KiB

joi2019_ho_t4

//
// 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";
}

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