Submission #1061059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061059		vjudge1	전선 연결 (IOI17_wiring)	C++17	20 / 100	1092 ms	38116 KiB

wiring

#include "wiring.h"
#include <set>
#include <iostream>
#include <map>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) 
{
	if (r.back()<b.front())
	{
		int x=min(r.size(),b.size());
		long long ans=0;
		for (int i=0;i<x;i++)
			ans+=abs(b[i]-r[i]);
		for (int i=x;i<r.size();i++)
			ans+=min(abs(b.back()-r[i]),abs(b[0]-r[i]));
		for (int i=x;i<b.size();i++)
			ans+=min(abs(b[i]-r.front()),abs(b[i]-r.back()));
		return ans;
	}
	int n=r.size(),m=b.size();
	map<pair<int,int>,int>dp;
	set<vector<int>>S;
	S.insert({0,0,0});
	dp[{0,0}]=0;
	while (S.size())
	{
		int i=(*begin(S))[1],j=(*begin(S))[2],co=(*begin(S))[0];
		S.erase(*begin(S));
		if (dp[{i,j}]!=co)
			continue;
		if (i==n&&j==m)
			break;
		if (i==n||j==m)
			continue;
		if (dp[{i+1,j+1}]==0)
		{
			dp[{i+1,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
			S.insert({dp[{i+1,j+1}],i+1,j+1});
		}
		if (dp[{i+1,j}]==0)
		{
			dp[{i+1,j}]=dp[{i,j}]+abs(r[i]-b[j]);
			S.insert({dp[{i+1,j}],i+1,j});
		}
		if (dp[{i,j+1}]==0)
		{
			dp[{i,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
			S.insert({dp[{i,j+1}],i,j+1});
		}
		int cost=dp[{i,j}]+abs(r[i]-b[j]);
		if (dp[{i+1,j+1}]>cost)
		{
			dp[{i+1,j+1}]=cost;
			S.insert({dp[{i+1,j+1}],i+1,j+1});
		}
		if (dp[{i+1,j}]>cost)
		{
			dp[{i+1,j}]=cost;
			S.insert({dp[{i+1,j}],i+1,j});
		}
		if (dp[{i,j+1}]>cost)
		{
			dp[{i,j+1}]=cost;
			S.insert({dp[{i,j+1}],i,j+1});
		}
	}
	// cout<<dp[{1,1}]<<endl;
	return dp[{n,m}];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int i=x;i<r.size();i++)
      |                ~^~~~~~~~~
wiring.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int i=x;i<b.size();i++)
      |                ~^~~~~~~~~

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