Submission #1274824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274824		kaiboy	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	30 ms	1216 KiB

joi2019_ho_t4

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100000;

int kk0[N], kk1[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	long long s = 0;
	for (int h = 0; h < n * 2; h++) {
		int x, y; cin >> x >> y, x--, y--;
		if (x < 0)
			s += -x, x = 0;
		else if (x > n - 1)
			s += x - (n - 1), x = n - 1;
		if (y < 0)
			s += -y, y = 0;
		else if (y > 1)
			s += y - 1, y = 1;
		(y ? kk1 : kk0)[x]++;
	}
	for (int k0 = 0, k1 = 0, i = 0; i < n; i++) {
		s += abs(k0) + abs(k1);
		k0 += kk0[i] - 1, k1 += kk1[i] - 1;
		if (k0 > 0 && k1 < 0) {
			int k = min(k0, -k1);
			s += k, k0 -= k, k1 += k;
		} else if (k0 < 0 && k1 > 0) {
			int k = min(-k0, k1);
			s += k, k0 += k, k1 -= k;
		}
	}
	cout << s << '\n';
	return 0;
}

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