Submission #561804

#	Time	Username	Problem	Language	Result	Execution time	Memory
561804		aryan12	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	96 ms	8652 KiB

joi2019_ho_t4

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
	int n;
	cin >> n;
	vector<vector<int> > cnt(n + 2, vector<int> (3, -1));
	int ans = 0;
	for(int i = 1; i <= n * 2; i++)
	{
		int x, y;
		cin >> x >> y;
		if(x <= 0)
		{
			ans += 1 - x;
			x = 1;
		}
		if(x > n)
		{
			ans += x - n;
			x = n;
		}
		if(y <= 0)
		{
			ans += 1 - y;
			y = 1;
		}
		if(y > 2)
		{
			ans += y - 2;
			y = 2;
		}
		cnt[x][y]++;
	}
	for(int i = 1; i <= n; i++)
	{
		if(cnt[i][1] < 0 && cnt[i][2] > 0)
		{
			int diff = min(-cnt[i][1], cnt[i][2]);
			ans += diff;
			cnt[i][1] += diff;
			cnt[i][2] -= diff;
		}
		if(cnt[i][1] > 0 && cnt[i][2] < 0)
		{
			int diff = min(cnt[i][1], -cnt[i][2]);
			ans += diff;
			cnt[i][1] -= diff;
			cnt[i][2] += diff;
		}
		ans += abs(cnt[i][1]) + abs(cnt[i][2]);
		cnt[i + 1][1] += cnt[i][1];
		cnt[i + 1][2] += cnt[i][2];
	}
	cout << ans << "\n";
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

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