제출 #428846

#제출 시각아이디문제언어결과실행 시간메모리
428846AmineWeslatiWiring (IOI17_wiring)C++14
0 / 100
1093 ms3796 KiB
#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);
}
#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...