Submission #1241340

#TimeUsernameProblemLanguageResultExecution timeMemory
1241340lovrotWiring (IOI17_wiring)C++20
7 / 100
14 ms2376 KiB
//#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);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...