Submission #420571

#	Time	Username	Problem	Language	Result	Execution time	Memory
420571		AugustinasJucas	Wiring (IOI17_wiring)	C++14	7 / 100	31 ms	6104 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
vector<int> r, b;
const int inf = 1e9;
long long linf = 1e18;
pair<int, int> closest(int a, vector<int> &b){
	auto desn = lower_bound(b.begin(), b.end(), a) - b.begin();
	if(desn == (int)b.size()){
		return {b[desn-1], inf};
	}else if(desn == 0){
		return {-inf, b[desn]};
	}else{
		return {b[desn-1], b[desn]};
	}
}
long long dp[201][201] = {};
long long min_total_length(vector<int> r, vector<int> b) {
	bool don[401] = {0};
	long long ans = 0;
	int n  = r.size(); int m = b.size();
	for(int i = 0; i < 201; i++) for(int j = 0; j < 201; j++) dp[i][j] = linf;
	dp[0][0] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i + j == 0) continue;
			// abu naujus
			int prm = r[i-1];
			int ant = b[j-1];
			dp[i][j] = min(dp[i][j], abs(prm-ant) + dp[i-1][j-1]);
			// R nauja
			
			dp[i][j] = min(dp[i][j], abs(r[i-1] - b[j-1]) + dp[i-1][j]);
			// B nauja
			
			dp[i][j] = min(dp[i][j], abs(r[i-1] - b[j-1]) + dp[i][j-1]);
		}
	}
	return dp[n][m];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:7: warning: unused variable 'don' [-Wunused-variable]
   21 |  bool don[401] = {0};
      |       ^~~
wiring.cpp:22:12: warning: unused variable 'ans' [-Wunused-variable]
   22 |  long long ans = 0;
      |            ^~~

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