Submission #122862

#	Time	Username	Problem	Language	Result	Execution time	Memory
122862		Sorting	Wiring (IOI17_wiring)	C++14	0 / 100	2 ms	376 KiB

wiring

#include <bits/stdc++.h>

using namespace std;

const int N = 2007;
const long long inf = 1e18;

int n, m;
pair<long long, bool> dp[N][N];
int x[N], y[N];

long long solve(int pos1, int pos2){
	if(pos1 >= n){
		if(pos2 >= m){
			return 0;
		}

		return inf;
	}
	if(pos2 >= m){
		return inf;
	}

	pair<long long, bool> &p = dp[pos1][pos2];

	if(p.second){
		return p.first;
	}

	p.second = true;
	
	p.first = max(solve(pos1 + 1, pos2 + 1), max(solve(pos1 + 1, pos2), solve(pos1, pos2 + 1))) + abs(x[pos1] - y[pos2]);

	return p.first;
}

long long min_total_length(vector<int> r, vector<int> b){
	n = (int)r.size();
	m = (int)b.size();

	for(int i = 0; i < n; i++){
		x[i] = r[i];
	}
	for(int i = 0; i < m; i++){
		y[i] = b[i];
	}

	return solve(0, 0);
}

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