Submission #928518

#	Time	Username	Problem	Language	Result	Execution time	Memory
928518		guechotjrhh	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	131 ms	7252 KiB

joi2019_ho_t4

#include<iostream>
#include<vector>
using namespace std;

long long arrangeCandles(int N, vector<int> X, vector<int> Y) {
	long long s = 0;
	vector<int> u1(N,0), d1(N,0);
	for (int i = 0; i < 2 * N; i++) {
		if (X[i] <= 1) { s += 1-X[i]; X[i] = 1; }
		if (X[i] >= N) { s += X[i]-N; X[i] = N; }

		if (Y[i] <= 1) { s += 1 - Y[i]; d1[X[i] - 1]++; }
		else { s += Y[i] - 2; u1[X[i] - 1]++; }
	}

    int u = 0, d = 0;
    for (int i = 0; i < N; i++) {
        int a = u1[i], b = d1[i];
        u += a - 1; d += b - 1;
        if (d < 0 && u>0) {
            if (abs(d) >= abs(u)) {
                d += u;
                s += u;
                u = 0;
            }
            else {
                u += d;
                s += abs(d);
                d = 0;
            }
        }
        else if (d > 0 && u < 0) {
            if (abs(d) >= abs(u)) {
                d += u;
                s += abs(u);
                u = 0;
            }
            else {
                u += d;
                s += d;
                d = 0;
            }
        }
        s += abs(d) + abs(u);
    }

	return s;
}

int main() {
	int N;
    cin >> N;
	vector<int> X(2 * N), Y(2 * N);
	for (int i = 0; i < 2 * N; i++) {
		cin >> X[i] >> Y[i];
	}

	long long ans = arrangeCandles(N, move(X), move(Y));
	cout << ans << endl;

	return 0;
}
/*
3
0 0
0 4
4 0
2 1
2 5
-1 1

*/

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