Submission #1338423

#TimeUsernameProblemLanguageResultExecution timeMemory
1338423settopWiring (IOI17_wiring)C++20
7 / 100
1095 ms2088 KiB
#include "wiring.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=2e2+10;
const ll inf=1e16;
typedef pair<int,int> pii;

ll dp[MAXN][MAXN],cl1[MAXN],cl[MAXN];

long long min_total_length(std::vector<int> r, std::vector<int> b){
	int n=sz(r),m=sz(b); sort(all(r)); sort(all(b));
	fall(i,0,n-1){
		cl1[i]=inf;
		fall(j,0,m-1) cl1[i]=min(cl1[i],1ll*abs(r[i]-b[j]));
	}
	fall(j,0,m-1){
		cl[j]=inf;
		fall(i,0,n-1) cl[j]=min(cl[j],1ll*abs(r[i]-b[j]));
	}

	fall(i,0,n)
		fall(j,0,m) dp[i][j]=inf;
	dp[0][0]=0;
	fall(i,0,n)
		fall(j,0,m){
			if(max(i,j)==0) continue;
			if(i) dp[i][j]=dp[i-1][j]+cl1[i-1];
			if(j) dp[i][j]=min(dp[i][j],dp[i][j-1]+cl[j-1]);
			if(i && j) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+abs(r[i-1]-b[j-1]));
		}
	return dp[n][m];
}
#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...