Submission #380597

#	Time	Username	Problem	Language	Result	Execution time	Memory
380597		peijar	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	96 ms	10476 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 2e18;

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbPieces;
	cin >> nbPieces;

	vector<vector<int>> nbOcc(nbPieces+1, vector<int>(2));

	int sol(0);

	for (int i = 0; i < 2*nbPieces; ++i) 
	{
		int x, y;
		cin >> x >> y;
		int oldX(x), oldY(y);
		if (x < 1) x = 1;
		if (x > nbPieces) x = nbPieces;
		if (y < 1) y = 1;
		if (y > 2) y = 2;
		sol += abs(x-oldX)+ abs(y-oldY);
		nbOcc[x][y]++;
	}
	
	int delta[3] = {0, 0, 0};
	for (int x(1); x <= nbPieces; ++x)
	{
		sol += abs(delta[1]) + abs(delta[2]);
		for (int y(1); y <= 2; ++y)
			delta[y] += 1 - nbOcc[x][y];
		if (delta[1] * delta[2] < 0)
		{
			int t= delta[1] < 0 ? min(delta[2], -delta[1]) : min(delta[1], -delta[2]);
			sol += t;
			if (delta[1] < 0)
				delta[2] -= t, delta[1] += t;
			else
				delta[2] += t, delta[1] -= t;
		}
	}
	cout << sol << endl;
}

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