Submission #1266831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266831		witek_cpp	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	47 ms	7480 KiB

joi2019_ho_t4

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())

ll wnk = 0;

vector<vector<ll>> dziury;

ll dist(pair<ll, ll> a, pair<ll, ll> b) {
	return (abs(a.st - b.st) + abs(a.nd - b.nd));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pair<ll, ll>> punkty(2 * n); //na poc podaja x
	f(i, 0, 2 * n) cin >> punkty[i].st >> punkty[i].nd;
	dziury.resize(2, vector<ll>(n + 1, -1));
	f(i, 0, 2 * n) {
		punkty[i].nd--;
		ll y = ll(punkty[i].nd > 0);
		ll x = min(max((ll)1, punkty[i].st), (ll)n);
		//cout << "ind " << i << " zostaje zmieniony na    x: " << x << "    y: " << y << "\n";
		wnk += dist(punkty[i], {x, y});
		dziury[y][x]++;
	}
	/*cout << "wynik to " << wnk << "\n";
	f(j, 0, 2) {
		f(i, 1, n + 1) {
			cout << dziury[j][i] << " ";
		}
		cout << "\n";
	}*/
	vector<vector<ll>> pref(2, vector<ll>(n + 1));
	pref[0][0] = pref[1][0] = 0;
	f(i, 1, n + 1) {
		f(j, 0, 2) pref[j][i]=pref[j][i - 1] + dziury[j][i];
		if (pref[0][i] > 0) {
			if (pref[1][i] < 0) {
				ll val = min(abs(pref[1][i]), pref[0][i]);
				//cout << "mamy zamieszanie na ind " << i << " ind 0 jest wiekszy val to " << val << "\n";
				//cout << pref[0][i] << " " << pref[1][i] << "\n";
				wnk+=val;
				pref[0][i] -= val;
				pref[1][i] += val;
			}
		} else if (pref[1][i] > 0) {
			if (pref[0][i] < 0) {
				ll val = min(abs(pref[0][i]), pref[1][i]);
				//cout << "mamy zamieszanie na ind " << i << " ind 1 jest wiekszy val to " << val << "\n";
				//cout << pref[0][i] << " " << pref[1][i] << "\n";
				wnk+=val;
				pref[1][i] -= val;
				pref[0][i] += val;
			}
		}
	} 
	/*cout << "wynik po szacher macher to " << wnk << "\n";
	f(j, 0, 2) {
		f(i, 1, n + 1) {
			cout << pref[j][i] << " ";
		}
		cout << "\n";
	}*/
	f(i, 1, n + 1) {
		f(j, 0, 2) wnk += abs(pref[j][i]);
	}
	cout << wnk;
	return 0;
}

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