Submission #123186

#	Time	Username	Problem	Language	Result	Execution time	Memory
123186		Sorting	Wiring (IOI17_wiring)	C++14	20 / 100	37 ms	4636 KiB

wiring

#include <bits/stdc++.h>

using namespace std;

const int N = 2007;
const int MAXN = 1e5 + 7;
const long long inf = 1e18;

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

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 = min(solve(pos1 + 1, pos2 + 1), min(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];
	}

	if(n > 5000 || m > 5000){
		long long ans = 0;

		if(n <= m){
			for(int i = 0; i < n - 1; i++){
				ans += abs(r[i] - b[i]);
			}

			for(int i = n - 1; i < m; i++){
				ans += abs(r[n - 1] - b[i]);
			}
		}
		else{
			for(int i = 0; i < n - m + 1; i++){
				ans += abs(r[i] - b[0]);
			}

			for(int i = 0; i < m - 1; i++){
				ans += abs(r[i + n - m + 1] - b[i + 1]);
			}
		}

		return ans;
	}

	return solve(0, 0);
}

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