Submission #428846

#	Time	Username	Problem	Language	Result	Execution time	Memory
428846		AmineWeslati	Wiring (IOI17_wiring)	C++14	0 / 100	1093 ms	3796 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
//------------------------------------

const ll INF=1e18;
const int MX=200+10;

int N,M; 
vi a(MX),b(MX);
ll memo[MX][MX];

ll solve(int i, int j){
	if(i==N){
		if(j<M) return 1e18;
		return 0;
	}

	ll ind=memo[i][j];
	if(ind!=-1) return ind; 

	ll ans=1e18,val=0;

	if(j) ans=solve(i+1,j)+abs(b[j-1]-a[i]);
	/*FOR(k,max(0,j-1),M){
		val+=abs(b[k]-a[i]);
		ll x=solve(i+1,k+1)+val;
		if(x<ans) ans=x;
	}*/

	val=0;
	FOR(k,j,M){
		val+=abs(b[k]-a[i]);

		ll x=solve(i+1,k+1)+val;
		if(x<ans) ans=x;
	}


	return ind=ans; 
}


ll min_total_length(vi a, vi b) {
	N=sz(a),M=sz(b);
	FOR(i,0,N) ::a[i]=a[i];
	FOR(i,0,M) ::b[i]=b[i];

	memset(memo,-1,sizeof(memo));
	return solve(0,0);
}

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