Submission #1241340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241340		lovrot	Wiring (IOI17_wiring)	C++20	7 / 100	14 ms	2376 KiB

wiring

//#include "wiring.h"
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdio>

#define PB push_back

using namespace std;

typedef long long ll;

const int N = 210;
const ll OO = 1e18;

int n, m, a[N], b[N];
ll dp[N][N];

ll _abs(ll x) { return x < 0 ? -x : x; }

ll phi(int l, int r) { 
	if(l >= n && r >= m) { return 0; }
	if(l >= n || r >= m) { return OO; }
	if(dp[l][r] != -1) { return dp[l][r]; }
	dp[l][r] = _abs(a[l] - b[r]) + min({phi(l + 1, r + 1), phi(l + 1, r), phi(l, r + 1)});
	return dp[l][r];
}

ll long min_total_length(vector<int> av, vector<int> bv) {
	memset(dp, -1, sizeof(dp));
	n = av.size();
	m = bv.size();
	for(int i = 0; i < n; ++i) { a[i] = av[i]; }
	for(int i = 0; i < m; ++i) { b[i] = bv[i]; }

	return phi(0, 0);
}

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