Submission #741767

#	Time	Username	Problem	Language	Result	Execution time	Memory
741767		MODDI	Wiring (IOI17_wiring)	C++14	100 / 100	38 ms	7100 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;

ll min_total_length(vector<int> red, vector<int> blue){
	ll ans = 0;
	int n = red.size(), m = blue.size();
	vector<array<int, 2> > arr;
	for(int i = 0, j = 0; i < n || j < m;){
		if(i < n && (j == m || red[i] < blue[j]))
			arr.pb({red[i++], 0});
		else
			arr.pb({blue[j++],1});
	}
	vector<ll> dp(n + m + 1, 1e16);
	dp[0] = 0;
	for(int i = 0, j = 0, k = 0; j < n + m; i = j, j = k){
		while(k < n + m && arr[k][1] == arr[j][1])	k++;
		for(int p = i; p < j; p++){
			dp[p+1] = min(dp[p+1], dp[p] + arr[j][0] - arr[p][0]);
		}
		ll sum = 0;
		for(int p = 0; j + p < k && j - 1 - p >= i; p++){
			sum += arr[j+p][0] - arr[j-1-p][0];
			dp[j+p+1] = min(dp[j+p+1], dp[j-1-p] + sum);
		}
		if(j > 0){
			for(int p = j; p < k; p++){
				dp[p+1] = min(dp[p+1], dp[p] + arr[p][0] - arr[j-1][0]);
			}
		}
	}
	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:10:5: warning: unused variable 'ans' [-Wunused-variable]
   10 |  ll ans = 0;
      |     ^~~

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