Submission #256949

#	Time	Username	Problem	Language	Result	Execution time	Memory
256949		GREGOIRELC	Wiring (IOI17_wiring)	C++14	7 / 100	39 ms	6280 KiB

wiring

#include "wiring.h"
#include <cmath>
#include <iostream>	

using namespace std;

//#define int long long

const int MAX_POINT = 200 + 2;
const int INF = 1e9 + 7;

int nbRouge, nbBleu;
long long dp[MAX_POINT][MAX_POINT];
vector<pair<int, int> > position;

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	nbRouge = (int)r.size();
	nbBleu = (int)b.size();
	for(int curRouge = 0; curRouge <= nbRouge; curRouge++)
	{
		for(int curBleu = 0; curBleu <= nbBleu; curBleu++)
		{
			dp[curRouge][curBleu] = INF;
		}
	}
	dp[0][0] = 0;
	for(int curRouge = 0; curRouge <= nbRouge; curRouge++)
	{
		for(int curBleu = 0; curBleu <= nbBleu; curBleu++)
		{
			//cout << curRouge << " " << curBleu << " " << dp[curRouge][curBleu] << endl;
			if(curBleu != 0)
			{
				dp[curRouge + 1][curBleu] = min(dp[curRouge + 1][curBleu], dp[curRouge][curBleu] + abs(r[curRouge] - b[curBleu - 1]));
			}
			if(curRouge != 0)
			{
				dp[curRouge][curBleu + 1] = min(dp[curRouge][curBleu + 1], dp[curRouge][curBleu] + abs(r[curRouge - 1] - b[curBleu]));
			}
			dp[curRouge + 1][curBleu + 1] = min(dp[curRouge + 1][curBleu + 1], dp[curRouge][curBleu] + abs(r[curRouge] - b[curBleu]));
		}
	}
	return dp[nbRouge][nbBleu];
}

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