Submission #317883

#	Time	Username	Problem	Language	Result	Execution time	Memory
317883		fefe	Wiring (IOI17_wiring)	C++17	0 / 100	55 ms	13056 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define abs(x) ((x) > 0 ? (x) : (-(x)))
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pil;
const int MAX_N = 100005;
const LL inf = (1LL<<60);
LL sum_r[MAX_N], sum_b[MAX_N];
int idx[2 * MAX_N];
LL t[2 * MAX_N];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = r.size();
	int m = b.size();
	for(int i=1;i<=n + m;i++)	t[i] = inf;
	for(int i=0;i<2 * MAX_N;i++)	idx[i] = -1;
	for(int i=1;i<=n;i++)	sum_r[i] = sum_r[i - 1] + r[i - 1];
	for(int i=1;i<=m;i++)	sum_b[i] = sum_b[i - 1] + b[i - 1];
	idx[MAX_N] = 0;
	int sum_idx = MAX_N;
	for(int i=0, j=0 ; i<n || j<m ; ){
		if(j == m || r[i] < b[j]){
			if(j != 0)	t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(r[i] - b[j - 1]));
			if(j < m)	t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(r[i] - b[j]));
			sum_idx++;
			i++;
		}else{
			if(i != 0)	t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(b[j] - r[i - 1]));
			if(i < n)	t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(b[j] - r[i]));
			sum_idx--;
			j++;
		}
		if(idx[sum_idx] == -1){
			idx[sum_idx] = i + j;
			continue;
		}
		int l = ((i + j) - idx[sum_idx]) / 2;
		t[i + j] = min(t[i + j], t[idx[sum_idx]] + abs((sum_r[i] - sum_r[i - l]) - (sum_b[j] - sum_b[j - l])));
		idx[sum_idx] = i + j;
	}
	return t[n + m];
}

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