Submission #649446

#	Time	Username	Problem	Language	Result	Execution time	Memory
649446		ymm	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	52 ms	5688 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
int a[2][N];
int n;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	memset(a, -1, sizeof(a));
	ll ans = 0;
	cin >> n;
	Loop (i,0,2*n) {
		int x, y;
		cin >> x >> y;
		if (x < 1) {
			ans += 1-x;
			x = 1;
		}
		if (x > n) {
			ans += x-n;
			x = n;
		}
		if (y < 1) {
			ans += 1-y;
			y = 1;
		}
		if (y > 2) {
			ans += y-2;
			y = 2;
		}
		a[y-1][x-1]++;
	}
	Loop (i,0,n) {
		if ((a[0][i] < 0) != (a[1][i] < 0)) {
			int mv = min(abs(a[0][i]), abs(a[1][i]));
			ans += mv;
			a[0][i] += a[0][i] < 0? mv: -mv;
			a[1][i] += a[1][i] < 0? mv: -mv;
		}
		ans += abs(a[0][i]) + abs(a[1][i]);
		a[0][i+1] += a[0][i];
		a[1][i+1] += a[1][i];
	}
	cout << ans << '\n';
}

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