Submission #137137

#	Time	Username	Problem	Language	Result	Execution time	Memory
137137		MAMBA	Wiring (IOI17_wiring)	C++17	0 / 100	55 ms	7464 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()

typedef long long ll;

ll min_total_length(std::vector<int> R, std::vector<int> b) {
	
	int n = R.size() + b.size();

	vector<int> mg(n);
	vector<ll> dp[3];

	dp[0] = dp[1] = dp[2] = vector<ll>(n + 1 , (ll)1e18);

	merge(all(R) , all(b) , mg.begin());

	dp[0][0] = 0;
	int last = 0;
	
	auto Tp = [&](int id) -> bool {
		return binary_search(all(R) , mg[id]);
	};

	auto solve = [&](int l , int r) {
		rep(X , 0 , 3)
			rep(Y , 0 , 3) {
				if (l == 0 && X) continue;
				if (r == n && Y) continue;
				if (!X && !Y) continue;
				ll local = dp[X][l];
				rep(i , l , r) {
					if (!X) {
						if (Y == 1) {
							local += mg[r] - mg[i];
						}
						else {
							if (r - l == 1) local += mg[r] - mg[r - 1];
							if (i != r - 1)
								local += mg[r] - mg[i];
						}
					}
					else if (X == 1) {
						if (!Y) {
							if (i > l)
								local += mg[i] - mg[l - 1];
						}
						else if (Y == 1) {
							if (i == r - 1)
								local += mg[r] - mg[r - 1];
							if (i > l && i < r - 1)
								local += min(mg[r] - mg[i] , mg[i] - mg[l - 1]);
						}
						else {
							if (r - l == 1)
								local += mg[r] - mg[r - 1];
							if (i < r - 1) {
								if (i == r - 2)
									local += mg[r] - mg[r - 2];
								if (i > l && i < r - 2)
									local +=  min(mg[r] - mg[i] , mg[i] - mg[l - 1]);
							}
						}
					}
					else {
						if (!Y) {
							if (r - l  == 1) local += mg[l] - mg[l - 1];
							if (i > l)
									local += mg[i] - mg[l - 1];
						}
						else if (Y == 1) {
							if (i == r - 1) local += mg[r] - mg[r - 1];
							if (r - l == 1) local += mg[l] - mg[l - 1];
							if (i == l + 1) local += mg[l + 1] - mg[l - 1];
							if (i > l + 1 && i < r - 1)
								local +=  min(mg[r] - mg[i] , mg[i] - mg[l - 1]);
						}
						else {
							if (r - l == 1) {
								local += mg[r] - mg[r - 1];
								local += mg[l] - mg[l - 1];
							}
							if (i == l + 1)
								local += mg[l + 1] - mg[l - 1];
							if (i == r - 2)
								local += mg[r] - mg[r - 2];
							if (i > l + 1 && i < r - 1)
								local +=  min(mg[r] - mg[i] , mg[i] - mg[l - 1]);
						}
					}
				}
				dp[Y][r] = min(dp[Y][r] , local);
			}
		last = r;
	};


	rep(i , 0 , n) 
		if (last < i && Tp(last) != Tp(i)) {
			solve(last , i);
		}

	solve(last , n);

	return dp[0][n];

}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45