Submission #1073940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073940		LCJLY	Wiring (IOI17_wiring)	C++14	7 / 100	21 ms	5440 KiB

wiring

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

#define int long long
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;

int arr[205];
int arr2[205];
int n=0;
int m=0;

int memo[205][205];

int dp(int l, int r){
	if(l==n||r==m){
		if(l==n&&r==m) return 0;
		else return 1e17;
	}
	if(memo[l][r]!=-1) return memo[l][r];
	int ans=1e17;
	ans=min(ans,dp(l+1,r)+abs(arr[l]-arr2[r]));
	ans=min(ans,dp(l,r+1)+abs(arr[l]-arr2[r]));
	ans=min(ans,dp(l+1,r+1)+abs(arr[l]-arr2[r]));
	return memo[l][r]=ans;
}

long long min_total_length(vector<int32_t>r, vector<int32_t>b) {
	n=r.size();
	m=b.size();
	for(int x=0;x<n;x++) arr[x]=r[x];
	for(int x=0;x<m;x++) arr2[x]=b[x];
	memset(memo,-1,sizeof(memo));
	return dp(0,0);
}

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