Submission #494774

#	Time	Username	Problem	Language	Result	Execution time	Memory
494774		Haruto810198	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	204 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n;
pii pt[MAX];
int tx[MAX];
int res;

int dp[3], newdp[3];

inline int C2(int x){
	return x * (x-1) / 2;
}

inline int cost(int st, int l, int r){
	if(l > r) return 0;
	int ret = 0, len = r - l + 1;
	if(st < l) ret += len * (l - st), st = l;
	if(st > r) ret += len * (st - r), st = r;
	int ll = st - l, rr = r - st;
	ret += C2(ll+1) + C2(rr+1);
	return ret;
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	FOR(i, 1, 2*n, 1){
		cin>>pt[i].F>>pt[i].S;
		tx[i] = (i + 1) / 2;
	}
	
	sort(pt+1, pt+2*n+1);

	vector<vector<pii>> groups;
	vector<pii> tmp = {pt[1]};
	int pv = pt[1].S;

	FOR(i, 2, 2*n, 1){
		if(pt[i].F != pv){
			pv = pt[i].F;
			sort(tmp.begin(), tmp.end());
			groups.pb(tmp);
			tmp.clear();
		}
		tmp.pb(pt[i]);
	}
	
	if(!tmp.empty()) groups.pb(tmp);
	
	dp[0] = 0;
	dp[1] = LNF;
	dp[2] = LNF;

	int psum = 0;
	
	for(vector<pii> G : groups){
		int sz = szof(G);
		int st = G[0].F;
		int owo;
		int ll = psum / 2, rr = (psum + sz) / 2;

		int sum_1 = 0, sum0 = 0, sum1 = 0;
		
		FOR(i, 0, sz/2 - 2, 1) sum_1 += abs(G[i].S - 1);
		FOR(i, sz/2 - 1, sz-1, 1) sum_1 += abs(G[i].S - 2);
		
		FOR(i, 0, sz/2 - 1, 1) sum0 += abs(G[i].S - 1);
		FOR(i, sz/2, sz-1, 1) sum0 += abs(G[i].S - 2);
		
		FOR(i, 0, sz/2, 1) sum1 += abs(G[i].S - 1);
		FOR(i, sz/2 + 1, sz-1, 1) sum1 += abs(G[i].S - 2);

		
		FOR(i, 0, 2, 1) newdp[i] = LNF;
		
		if(dp[0] < LNF){
			if(sz % 2 == 0){
				// 0 -> 0
				owo = dp[0] + sum0 + 2 * cost(st, ll + 1, rr);
				newdp[0] = min(newdp[0], owo);
			}
			else{
			 	// 0 -> 1
				owo = dp[0] + sum1 + cost(st, ll + 1, rr) + cost(st, ll + 1, rr + 1);
				newdp[1] = min(newdp[1], owo);
				
				// 0 -> 2
				owo = dp[0] + sum0 + cost(st, ll + 1, rr) + cost(st, ll + 1, rr + 1);
				newdp[2] = min(newdp[2], owo);
			}
		}
		else{
			if(sz % 2 == 0){
				// 1 -> 2
				owo = dp[1] + sum_1 + cost(st, ll + 2, rr) + cost(st, ll + 1, rr + 1);
				newdp[2] = min(newdp[2], owo);

				// 1 -> 1, 2 -> 2
				owo = dp[1] + sum0 + cost(st, ll + 2, rr + 1) + cost(st, ll + 1, rr);
				newdp[1] = min(newdp[1], dp[1] + owo);
				owo = dp[2] + sum0 + cost(st, ll + 2, rr + 1) + cost(st, ll + 1, rr);
				newdp[2] = min(newdp[2], dp[2] + owo);
				
				// 2 -> 1
				owo = dp[2] + sum1 + cost(st, ll + 1, rr) + cost(st, ll + 2, rr - 1);
				newdp[1] = min(newdp[1], owo);
			}
			else{
				// 1 -> 0
				owo = dp[1] + sum0 + cost(st, ll + 2, rr) + cost(st, ll + 1, rr);
				newdp[0] = min(newdp[0], owo);

				// 2 -> 0
				owo = dp[2] + sum1 + cost(st, ll + 2, rr) + cost(st, ll + 1, rr);
				newdp[0] = min(newdp[0], owo);
			}
		}

		FOR(i, 0, 2, 1) dp[i] = newdp[i];
		/*
		FOR(i, 0, 2, 1){
			cerr<<"dp["<<i<<"] = ";
			if(dp[i] < LNF) cerr<<dp[i]<<" ";
			else cerr<<"- ";
		}
		
		cerr<<"G : ";
		for(int i : G){
			cerr<<i<<" ";
		}
		
		cerr<<endl;
		*/
		psum += sz;
	}
	
	res += dp[0];
	cout<<res<<'\n';
	
	return 0;

}

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