Submission #137252

#	Time	Username	Problem	Language	Result	Execution time	Memory
137252		random0029	Wiring (IOI17_wiring)	C++14	100 / 100	101 ms	21992 KiB

wiring

// ItnoE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
const ll INF = 1e15;
int n;
vector < ll > P[N], S[N], dp[N];
inline void smin(ll &a, ll b) {a = min(a, b);}
int64_t min_total_length(vector < int > R, vector < int > B)
{
	vector < pair < int , int > > A;
	for (int r : R)
		A.push_back({r, 0});
	for (int b : B)
		A.push_back({b, 1});
	sort(A.begin(), A.end());
	for (int i = 0; i < (int)A.size();)
	{
		int r = i;
		while (r < (int)A.size() && A[r].second == A[i].second)
			r ++;
		P[n].push_back(0);
		S[n].push_back(0);
		for (int j = i; j < r; j ++)
			P[n].push_back(P[n].back() + A[j].first);
		for (int j = r - 1; j >= i; j --)
			S[n].push_back(S[n].back() + A[j].first);
		dp[n] = vector < ll > (r - i + 1, INF);
		n ++; i = r;
	}
	dp[0][(int)dp[0].size() - 1] = 0;
	for (int i = 0; i < n; i ++)
	{
		int sz = (int)dp[i].size();
		if (i > 0)
		{
			for (int j = sz - 1; j > 0; j --)
			{
				ll sm = S[i][j] - S[i][j - 1];
				sm -= S[i - 1][1];
				smin(dp[i][j - 1], dp[i][j] + sm);
			}
		}
		for (int j = 1; j < sz; j ++)
		{
			ll lst = S[i][j] - S[i][j - 1];
			ll now = P[i][1];
			smin(dp[i][j], dp[i][j - 1] - lst + now);
		}
		if (i + 1 >= n)
			continue;
		for (int j = 0; j < sz; j ++)
		{
			//for (int k = 0; k <= j && k < (int)dp[i + 1].size(); k ++)
			{
				int jj = min(j, (int)P[i + 1].size() - 1);
				ll sm = P[i + 1][jj] + P[i + 1][1] * (ll)(j - jj);
				sm -= S[i][j];
				smin(dp[i + 1][(int)dp[i + 1].size() - 1 - jj], dp[i][j] + sm);
			}
		}
	}
	return (dp[n - 1][0]);
}
/*int main()
{
	int rr, bb, a;
	vector < int > RR, BB;
	cin >> rr >> bb;
	for (int i = 0; i < rr; i ++)
		cin >> a, RR.push_back(a);
	for (int i = 0; i < bb; i ++)
		cin >> a, BB.push_back(a);
	ll res = min_total_length(RR, BB);
	cout << res << endl;
}*/

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