Submission #415427

#	Time	Username	Problem	Language	Result	Execution time	Memory
415427		SeDunion	Wiring (IOI17_wiring)	C++17	100 / 100	95 ms	21940 KiB

wiring

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

int n, m;

ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size();
	m = b.size();
	vector<pair<int,int>>all;
	for (int i : r) all.emplace_back(i, 0);
	for (int i : b) all.emplace_back(i, 1);
	sort(all.begin(), all.end());
	vector<vector<ll>>gr;
	for (int i = 0 ; i < n + m ; ) {
		int j = i;
		while (j < n + m && all[i].second == all[j].second) ++j;
		gr.emplace_back();
		for (; i < j ; ++ i) {
			gr.back().emplace_back(all[i].first);
			//cerr << all[i].first << " ";
		}
		//cerr << "=======\n";
	}
	int sz = gr.size();
	vector<vector<ll>>dp(sz);
	vector<int>g(sz);
	vector<vector<ll>>p(sz), s(sz);
	for (int i = 0 ; i < sz ; ++ i) {
		dp[i].assign((int)gr[i].size() + 1, inf);
		g[i] = gr[i].size();
		p[i].assign((int)gr[i].size() + 1, 0);
		for (int j = 1 ; j <= g[i] ; ++ j) {
			p[i][j] = p[i][j - 1] + gr[i][j - 1];
		}
		s[i].assign((int)gr[i].size() + 1, 0);
		for (int j = 1 ; j <= g[i] ; ++ j) {
			s[i][j] = s[i][j - 1] + gr[i][g[i] - j];
		}
	}
	dp[0][g[0]] = 0;
	for (int i = 0 ; i < sz ; ++ i) {
		for (int j = g[i] ; j > 0 ; -- j) {
			if (i + 1 < sz && j <= g[i + 1]) {
				dp[i + 1][g[i + 1] - j] = min(dp[i + 1][g[i + 1] - j], dp[i][j] + p[i + 1][j] - s[i][j]);
			}
			if (i + 1 < sz) {
				dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + gr[i + 1][0] - gr[i][g[i]-j]);
			} 
			if (i > 0) {
				dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + gr[i][g[i]-j] - gr[i - 1][g[i - 1]-1]);
			}
		}
		if (i + 1 < sz) dp[i + 1][g[i + 1]] = min(dp[i + 1][g[i + 1]], dp[i][0]);
	}
	return dp[sz-1][0];
}

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