Submission #1322567

#TimeUsernameProblemLanguageResultExecution timeMemory
1322567JuanJLWiring (IOI17_wiring)C++20
7 / 100
22 ms8604 KiB
#include "wiring.h"
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b;i++)
#define mset(a,v) memset(a,v,sizeof(a))

using namespace std;
typedef long long ll;

const int MAXN = 200+5;
const ll INF = 10000000000000000;
vector<ll> red;
vector<ll> blu;

ll dp[MAXN][MAXN];
ll f(ll x, ll y){
	ll &res=dp[x][y];
	if(res!=-1) return res;
	if(x==SZ(red) && y==SZ(blu)) return 0;
	if(x==SZ(red)) return INF;
	if(y==SZ(blu)) return INF;
	res=INF;
	res=min(f(x+1,y),min( f(x+1,y+1),f(x,y+1) ))+abs(red[x]-blu[y]);
	return res;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	mset(dp,-1);
	red.clear(); forn(i,0,SZ(r)) red.pb(r[i]);
	blu.clear(); forn(i,0,SZ(b)) blu.pb(b[i]);
	sort(ALL(red));
	sort(ALL(blu));

	return f(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...