Submission #45344

#	Time	Username	Problem	Language	Result	Execution time	Memory
45344		Mamnoon_Siam	Wiring (IOI17_wiring)	C++17	20 / 100	67 ms	7088 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"

const int maxn = 100010;
typedef long long ll;
const ll inf = 1e18;

ll n, m;
ll p[maxn], q[maxn];
ll dp[202][202];

ll pro() {
	for(int i=1; i<=n; i++) dp[i][0] = inf;
	for(int i=1; i<=m; i++) dp[0][i] = inf;
	dp[0][0] = 0;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + abs(p[i]-q[j]);
		}
	} return dp[n][m];
}

ll lol() {
	ll ret = 0;
	for(int i=1; i<=n; i++) ret += p[n] - p[i];
	for(int i=1; i<=m; i++) ret += q[i] - q[1];
	ret += max(n, m) * (q[1] - p[n]);
	return ret;
}

ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size(), m = b.size();
	for(int i=1; i<=n; i++) p[i] = r[i-1];
	for(int i=1; i<=m; i++) q[i] = b[i-1];
	if(n <= 200 and m <= 200) return pro();
	return lol();
}

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