Submission #121276

#	Time	Username	Problem	Language	Result	Execution time	Memory
121276		youngyojun	Coin Collecting (JOI19_ho_t4)	C++11	0 / 100	3 ms	384 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define upmin(a,b) (a)=min((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1055;

pii P[MAXN*2];
int A[MAXN][2];

ll PreSum, Ans;
int N;

void process() {
	for(int key = 0; key < (1<<(N<<1)); key++) {
		int cnt = 0;
		for(int i = 0; i < N*2; i++) if(key & (1<<i)) cnt++;
		if(cnt != N) continue;

		ll ret = 0;
		int a = 1, b = 1;
		for(int i = 1; i <= N*2; i++) {
			if(key & (1<<(i-1))) {
				ret += abs(a - P[i].first) + P[i].second;
				a++;
			} else {
				ret += abs(b - P[i].first) + 1-P[i].second;
				b++;
			}
		}
		if(ret < Ans) Ans = ret;
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = N<<1, x, y; i--;) {
		cin >> x >> y;
		if(x < 1) {
			PreSum += 1-x;
			x = 1;
		}
		if(N < x) {
			PreSum += x-N;
			x = N;
		}
		if(2 < y) {
			PreSum += y-2;
			y = 2;
		}
		if(y < 1) {
			PreSum += 1-y;
			y = 1;
		}
		A[x][y-1]++;
	}
	for(int i = 1; i <= N; i++) {
		A[i][0]--; A[i][1]--;
	}

	for(int i = 1; i < N; i++) {
		if(0 <= A[i][0] && 0 <= A[i][1]) {
			Ans += A[i][0] + A[i][1];
		} else if(A[i][0] <= 0 && A[i][1] <= 0) {
			Ans -= A[i][0] + A[i][1];
		} else if(abs(A[i][0]) < abs(A[i][1])) {
			Ans += abs(A[i][0]);
			A[i][1] += A[i][0];
			A[i][0] = 0;
		} else {
			Ans += abs(A[i][1]);
			A[i][0] += A[i][1];
			A[i][1] = 0;
		}
		A[i+1][0] += A[i][0];
		A[i+1][1] += A[i][1];
	}
	Ans += abs(A[N][0]);

	cout << PreSum + Ans << endl;
	return 0;
}

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