제출 #1266815

#제출 시각아이디문제언어결과실행 시간메모리
1266815witek_cppCoin Collecting (JOI19_ho_t4)C++20
0 / 100
0 ms320 KiB
#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 > 1);
		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, 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 = max(abs(pref[1][i]), pref[0][i]);
				wnk+=val;
				pref[0][i] -= val;
				pref[1][i] += val;
			}
		} else if (pref[1][i] > 0) {
			if (pref[0][i] < 0) {
				ll val = max(abs(pref[0][i]), pref[1][i]);
				wnk+=val;
				pref[1][i] -= val;
				pref[0][i] += val;
			}
		}
	} 
	f(i, 1, n + 1) {
		f(j, 0, 2) wnk += abs(pref[j][i]);
	}
	cout << wnk;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...