Submission #492443

#	Time	Username	Problem	Language	Result	Execution time	Memory
492443		pavement	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	2 ms	2660 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, ans, X[100005], Y[100005], mem[100005][3];
ii T[100005];
map<int, int> maybe, cnt, rev;
map<int, vector<int> > M;

int cst(vector<int> &v, int n) {
	int ret = 0;
	for (int i = 0; i < n; i++) ret += llabs(v[i] - 1);
	for (int i = n; i < v.size(); i++) ret += llabs(v[i] - 2);
	return ret;
}

int dp(int n, int c) {
	if (n == 0) return 0;
	if (mem[n][c] != -1) return mem[n][c];
	int ret = -1;
	if (c == 0) {
		assert(maybe[rev[n]] <= 1);
		if (maybe[rev[n]] == 0) {
			assert(M[rev[n]].size() % 2 == 0);
			ret = dp(n - 1, 0) + cst(M[rev[n]], M[rev[n]].size() / 2);
		} else {
			assert(M[rev[n]].size() % 2 == 1);
			ret = min(dp(n - 1, 1) + cst(M[rev[n]], M[rev[n]].size() / 2), dp(n - 1, 2) + cst(M[rev[n]], M[rev[n]].size() / 2 + 1));
		}
	} else if (c == 1) {
		assert(1 <= maybe[rev[n]]);
		if (maybe[rev[n]] == 1) {
			assert(M[rev[n]].size() % 2 == 1);
			ret = dp(n - 1, 0) + cst(M[rev[n]], M[rev[n]].size() / 2 + 1);
		} else {
			assert(M[rev[n]].size() % 2 == 0);
			ret = min(dp(n - 1, 1) + cst(M[rev[n]], M[rev[n]].size() / 2), dp(n - 1, 2) + cst(M[rev[n]], M[rev[n]].size() / 2 + 1));
		}
	} else {
		assert(1 <= maybe[rev[n]]);
		if (maybe[rev[n]] == 1) {
			assert(M[rev[n]].size() % 2 == 1);
			ret = dp(n - 1, 0) + cst(M[rev[n]], M[rev[n]].size() / 2);
		} else {
			assert(M[rev[n]].size() % 2 == 0);
			ret = min(dp(n - 1, 1) + cst(M[rev[n]], M[rev[n]].size() / 2 - 1), dp(n - 1, 2) + cst(M[rev[n]], M[rev[n]].size() / 2));
		}
	}
	return mem[n][c] = ret;
}

main() {
	memset(mem, -1, sizeof mem);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N * 2; i++) {
		cin >> X[i] >> Y[i];
		T[i] = mp(X[i], Y[i]);
	}
	sort(T + 1, T + 1 + N * 2);
	for (int i = 1; i <= N * 2; i++) {
		tie(X[i], Y[i]) = T[i];
		M[X[i]].pb(Y[i]);
	}
	for (int i = 1, cnt = 1; i <= N * 2; i += 2, cnt++) {
		if (X[i] != X[i + 1]) {
			maybe[X[i]]++;
			maybe[X[i + 1]]++;
		}
		ans += llabs(X[i] - cnt) + llabs(X[i + 1] - cnt);
	}
	int idx = 0;
	for (auto i : M) {
		idx++;
		rev[idx] = i.first;
	}
	cout << ans + dp(M.size(), 0) << '\n';
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'long long int cst(std::vector<long long int>&, long long int)':
joi2019_ho_t4.cpp:36:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = n; i < v.size(); i++) ret += llabs(v[i] - 2);
      |                  ~~^~~~~~~~~~
joi2019_ho_t4.cpp: At global scope:
joi2019_ho_t4.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main() {
      | ^~~~

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