Submission #361947

#	Time	Username	Problem	Language	Result	Execution time	Memory
361947		NachoLibre	Wiring (IOI17_wiring)	C++17	13 / 100	132 ms	37084 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
#ifndef wambule
#include "wiring.h"
#else
#endif

const long long inf = 1e15;
long long min_total_length(vector<int> r, vector<int> b) {
	//  //  //  //  //  //  //  //
	int n = sz(r);
	int m = sz(b);
	vector<pair<int, int>> v;
	for(int i = 0; i < n; ++i) {
		v.push_back({r[i], 0});
	}
	for(int i = 0; i < m; ++i) {
		v.push_back({b[i], 1});
	}
	sort(v.begin(), v.end());
	vector<vector<int>> a;
	for(int i = 0; i < n + m; ++i) {
		if(i == 0 || v[i].second != v[i - 1].second) {
			a.push_back({0});
		}
		(--a.end())->push_back(v[i].first);
	}
	//  //  //  //  //  //  //  //
	n = sz(a);
	vector<vector<long long>> pj, sj;
	long long mj = 0;
	for(int i = 0; i < n; ++i) {
		pj.push_back(vector<long long>(sz(a[i])));
		sj.push_back(vector<long long>(sz(a[i])));
		mj = 0;
		for(int j = 2; j < sz(a[i]); ++j) {
			mj += a[i][j] - a[i][j - 1];
			pj[i][j] = pj[i][j - 1] + mj;
		}
		mj = 0;
		for(int j = sz(a[i]) - 2; j >= 1; --j) {
			mj += a[i][j + 1] - a[i][j];
			sj[i][j] = sj[i][j + 1] + mj;
		}
	}
	//  //  //  //  //  //  //  //
	vector<vector<long long>> fp, fg, fj, fgp, fjs;
	fp.resize(n);
	fg.resize(n);
	fgp.resize(n);
	fj.resize(n);
	fjs.resize(n);
	for(int i = 0; i < n; ++i) {
		fp[i].resize(sz(a[i]));
		fg[i].resize(sz(a[i]));
		fj[i].resize(sz(a[i]));
		fgp[i].resize(sz(a[i]));
		fjs[i].resize(sz(a[i]));
		//  //  //  //  //  //  //  //
		if(i) {
			long long md = a[i][1] - a[i - 1][sz(a[i - 1]) - 1];
			fp[i][0] = fp[i - 1][sz(a[i - 1]) - 1];
			for(int j = 1; j < sz(fp[i]); ++j) {
				if(sz(a[i - 1]) - 1 >= j) {
					if(fgp[i - 1][sz(a[i - 1]) - 1 - j] == inf) fp[i][j] = inf;
					else fp[i][j] = fgp[i - 1][sz(a[i - 1]) - 1 - j] + pj[i][j];
				} else {
					fp[i][j] = inf;
				}
				// if(i != 2 || j != 2)
				if(j > 1)
					fp[i][j] = min(fp[i][j], fjs[i - 1][max(0, sz(a[i - 1]) - j)] + pj[i][j] + md * j);
			}
		} else {
			fp[0][0] = 0;
			for(int i = 1; i < sz(fp[0]); ++i) {
				fp[0][i] = inf;
			}
		}
		//  //  //  //  //  //  //  //
		if(i < n - 1) {
			long long md = a[i + 1][1] - a[i][sz(a[i]) - 1];
			for(int j = 0; j < sz(fp[i]) - 1; ++j) {
				if(fp[i][j] == inf) {
					fj[i][j] = inf;
					fg[i][j] = inf;
				} else {
					fj[i][j] = fp[i][j] + sj[i][j + 1];
					fg[i][j] = fj[i][j] + md * (sz(fp[i]) - 1 - j);
				}
			}
			fgp[i][0] = fg[i][0];
			for(int j = 1; j < sz(fp[i]) - 1; ++j) {
				fgp[i][j] = min(fgp[i][j - 1], fg[i][j]);
			}
			fjs[i][sz(fp[i]) - 2] = fj[i][sz(fp[i]) - 2];
			for(int j = sz(fp[i]) - 3; j >= 0; --j) {
				fjs[i][j] = min(fjs[i][j + 1], fj[i][j]);
			}
		}
	}
	//  //  //  //  //  //  //  //
	#ifdef wambule
	cout << "|-[ a ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(a[i]); ++j) {
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	cout << "|-[ fp ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(fp[i]); ++j) {
			if(fp[i][j] == inf) cout << "inf ";
			else cout << fp[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	cout << "|-[ fj ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(fj[i]); ++j) {
			if(fj[i][j] == inf) cout << "inf ";
			else cout << fj[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	cout << "|-[ fg ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(fp[i]); ++j) {
			if(fg[i][j] == inf) cout << "inf ";
			else cout << fg[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	cout << "|-[ fjs ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(fj[i]); ++j) {
			if(fjs[i][j] == inf) cout << "inf ";
			else cout << fjs[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	cout << "|-[ fgp ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(fp[i]); ++j) {
			if(fgp[i][j] == inf) cout << "inf ";
			else cout << fgp[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	cout << "|-[ pj ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(fp[i]); ++j) {
			cout << pj[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	cout << "|-[ sj ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(fp[i]); ++j) {
			cout << sj[i][j] << " ";
		}
		cout << endl;
	}
	cout << "_____________" << endl;
	#endif
	//  //  //  //  //  //  //  //
	return fp[n - 1][sz(fp[n - 1]) - 1];
	//  //  //  //  //  //  //  //
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10}) << endl;
	return 0;
}
#endif

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