Submission #1198576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198576		dosts	전선 연결 (IOI17_wiring)	C++20	0 / 100	1097 ms	9748 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

const int inf = 1e18;
vi p;
vi a;
int get(int l,int r,int l2,int r2) {
	int n1 = r-l+1,n2 = r2-l2+1;
	int s1 = p[r]-p[l-1],s2 = p[r2]-p[l2-1];
	if (n2 >= n1) {
		return (s2-s1)-(n2-n1)*a[r];
	}
	else {
		return (n1-n2)*a[l2]+(s2-s1);
	}
}
int min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
	int n = r.size()+b.size();
	vector<pii> pts;
	for (auto it : r) pts.push_back({it,0});
	for (auto it : b) pts.push_back({it,1});
	sort(all(pts));
	p.assign(n+1,0);
	a.assign(n+1,0);
	for (int i=1;i<=n;i++) a[i] = pts[i-1].ff;
	for (int i=1;i<=n;i++) p[i] = p[i-1]+a[i];
	pii lst{-1,-1};
	vi dp(n+1,0);
	for (int i = 0;i<n;) {
		int j = i;
		while (j<n-1 && pts[j+1].ss == pts[i].ss) j++;
		//i..j
		for (int k = i;k<=j;k++) dp[k+1] = inf;
		if (lst != pii{-1,-1}) {
			int opt = lst.ss;
			for (int k = i;k<=j;k++) {
				int opty = opt;
				int best = 2e18;
				for (int tr = lst.ss; tr >= lst.ff; tr--) {
					if (dp[tr] == inf) continue;
					int cost = dp[tr]+get(tr+1,i,i+1,k+1);
					//cout << k sp tr sp dp[tr] sp cost << '\n';
					if (cost <= best) {
						best = cost;
						opt = tr;
					}
				}	
				dp[k+1] = best;			
			}
		}
		lst = {i,j};
		i = j+1;	
	}
	return dp[n];

}

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