Submission #288833

#	Time	Username	Problem	Language	Result	Execution time	Memory
288833		luciocf	Wiring (IOI17_wiring)	C++14	20 / 100	34 ms	2040 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
 
#define ff first
#define ss second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
const int maxn = 210;
const ll inf = 1e18+10;
 
int n, m;
 
ll dp[maxn][maxn];

int r[maxn], b[maxn];
 
ll solve(int i, int j)
{
	if ((i > n && j <= m) || (i <= n && j > m)) return inf;
	if (i == n+1 && j == m+1) return 0;
	if (dp[i][j] != -1) return dp[i][j];

	return dp[i][j] = abs(r[i]-b[j]) + min({solve(i+1, j), solve(i, j+1), solve(i+1, j+1)});
}
 
ll min_total_length(vector<int> R, vector<int> B)
{
	n = R.size(), m = B.size();
 
	if (n <= 200 && m <= 200)
	{
		for (int i = 0; i < n; i++)
			r[i+1] = R[i];
		for (int i = 0; i < m; i++)
			b[i+1] = B[i];
		
		memset(dp, -1, sizeof dp);
		return solve(1, 1);
	}
 
	ll ans = 0;
 
	if (m > n)
	{
		for (int i = m-1; i >= n; i--)
			ans += 1ll*(B[i]-R[n-1]);
 
		for (int i = n-1; i >= 0; i--)
			ans += 1ll*(B[i]-R[i]);
	}
	else if (m < n)
	{
		for (int i = 0; i < n-m; i++)
			ans += 1ll*(B[0]-R[i]);
 
		for (int i = n-m; i < n; i++)
			ans += 1ll*(B[i-(n-m)]-R[i]);
	}
	else
	{
		for (int i = 0; i < n; i++)
			ans += 1ll*(B[i]-R[i]);
	}
 
	return ans;
}

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