Submission #1054344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054344		Unforgettablepl	Wiring (IOI17_wiring)	C++17	17 / 100	1094 ms	7180 KiB

wiring

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

const int MAX_DIVERGENCE = 5;
const long long INF = 1e15;

long long min_total_length(vector<int> r, vector<int> b) {
	vector<pair<int,int>> arr;
	for(int&i:b)arr.emplace_back(i,0);
	for(int&i:r)arr.emplace_back(i,1);
	sort(arr.begin(), arr.end());
	int n = arr.size();
	arr.insert(arr.begin(),{-1,0});
	vector DP(n+1,INF);
	DP[0]=0;
	for(int i=1;i<=n;i++) {
		auto [idx,mycolour] = arr[i];
		long long minmy,maxother;
		int found = i;
		long long sum = 0;
		int cntMy = 0,cntOther = 0;
		for(int j=i;j;j--) {
			if(mycolour==arr[j].second) {
				cntMy++;
				minmy = arr[j].first;
				sum+=arr[j].first;
			} else {
				found = j;
				maxother=arr[j].first;
				break;
			}
		}
		if(found==i)continue;
		for(int j=found;j;j--) {
			if(arr[j].second==mycolour)break;
			cntOther++;
			sum-=arr[j].first;
			int edges = max(cntMy,cntOther);
			long long currcost = sum+(edges-cntMy)*minmy-(edges-cntOther)*maxother;
			DP[i]=min(DP[i],min(DP[j-1],DP[j])+currcost);
		}
	}
	return DP[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:40:42: warning: 'minmy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |    long long currcost = sum+(edges-cntMy)*minmy-(edges-cntOther)*maxother;
      |                             ~~~~~~~~~~~~~^~~~~~

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