제출 #598023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598023		Lucpp	전선 연결 (IOI17_wiring)	C++17	17 / 100	1098 ms	7144 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll solve2(vector<int> r, vector<int> b){
	int n = int(r.size()), m = int(b.size());
	ll ans = 0;
	for(int i = 0; i < m; i++) ans += b[i];
	for(int i = 0; i < n; i++) ans -= r[i];
	if(n < m) for(int i = 0; i < m-n; i++) ans -= r.back();
	if(m < n) for(int i = 0; i < n-m; i++) ans += b.front();
	return ans;
}

ll min_total_length(vector<int> r, vector<int> b) {
	int n = int(r.size()), m = int(b.size());
	vector<pair<int, int>> a;
	for(int i : r) a.emplace_back(i, 0);
	for(int i : b) a.emplace_back(i, 1);
	sort(a.begin(), a.end());
	vector<ll> dp(n+m+1);
	for(int i = 1; i <= n+m; i++){
		dp[i] = INF;
		vector<int> diff;
		int cnt = 0;
		for(int j = i-1; j >= 0; j--){
			if(diff.empty() || diff.back() != a[j].second){
				if((int)diff.size() == 2 && cnt > 1) break;
				if((int)diff.size() > 2) break;
				diff.push_back(a[j].second);
				cnt = 1;
			}
			else cnt++;
			if((int)diff.size() == 2){
				vector<int> x, y;
				for(int k = j; k < i; k++) if(a[k].second == diff[1]) x.push_back(a[k].first); else y.push_back(a[k].first);
				ll ans = solve2(x, y);
				dp[i] = min(dp[i], dp[j]+abs(ans));
			}
			else if((int)diff.size() == 3){
				int mid = diff[1];
				bool vis = false;
				ll ans = 0;
				for(int k = j; k < i; k++){
					if(a[k].second == mid){
						vis = true;
						ans += ll(k-j - (i-1-k))*a[k].first;
					}
					else{
						if(!vis) ans -= a[k].first;
						else ans += a[k].first;
					}
				}
				dp[i] = min(dp[i], dp[j]+ans);
			}
		}
	}
	return dp[n+m];
}

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