Submission #41316

#	Time	Username	Problem	Language	Result	Execution time	Memory
41316		alenam0161	Wiring (IOI17_wiring)	C++14	0 / 100	57 ms	13444 KiB

wiring

#define _CRT_SECURE_NO_WARNINGS
#include "wiring.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define sz(l,r)  (r-l+1)
#define sum(l,r) ((long long)((int)r>=(int)l ? (long long)(pre[r]-(l==0 ? 0ll:pre[l-1])):0ll) -sz(l,r)*val[l])
#define sum1(l,r) abs(((long long)((int)r>=(int)l ? (long long)(pre[r]-(l==0 ? 0ll:pre[l-1])):0ll) -sz(l,r)*val[r]))
const int N = 2e5 + 7;
struct seg {
	int tl,  tr;

};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<pair<int, int>> all;
	for (int to : r)all.push_back({ to,0 });
	for (int to : b)all.push_back({ to,1 });
	int n = all.size();
	sort(all.begin(), all.end());
	vector<int> kind, val,left(n,0);
	for (int i = 0; i < n; ++i) {
		kind.push_back(all[i].second);
		val.push_back(all[i].first);
		if (i == 0 || kind[i] != kind[i - 1]) {
			left[i] = i;
		}
		else left[i] = left[i - 1];
	}
	vector<long long> dp(n, (long long)1e18),pre(n,0),dpmx(n,(long long)1e18);
	for (int i = 0; i < n; ++i)if (i == 0)pre[i] = val[i]; else pre[i] = val[i] + pre[i - 1];
	int opt=-1;
	for (int i = 0; i < n; ++i) {
	//	cout << "current i = "<<i<<"  opt= "<<opt<<":\n"<< endl;
		if (left[i] == 0) {
			dp[i] = 0; continue;
		}
		auto gum=[&] (int l,  int r) {
			int m = left[r];
		//	cout << "left=="<<l<<" and Left of "<<r<<" is "<<m <<":\n"<< endl;
		//	cout << "sum(" << l << "," << m - 1 << ") = " << sum(l, m - 1) << endl;
		//	cout << "sum(" << m << "," << r << ") = " << sum(m,r) << endl;
			return sum1(l, m - 1) + sum(m, r) + max(sz(l, m - 1), sz(m, r))*(val[m]-val[m-1]);
		};
		if (left[left[i] - 1] == 0) {
			dp[i] = gum(left[left[i]-1],i);
		}
		else if (i == left[i]) {
			opt = left[left[i] - 1] + (left[left[i-1]-1]==0);
			for (; opt < left[i] - 1; ++opt) {
				if (gum(opt, i) + dpmx[opt - 1] >= gum(opt + 1, i) + dpmx[opt]) {
					continue;
				}
				break;
			}
			dp[i] = gum(opt, i) + dpmx[opt - 1];
		}
		else {
			int L = left[left[i] - 1];
			if (opt == L) {
				dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
			}
			else {
			//	cout << i << " " << opt << endl;
				if (left[i] - 1 - opt > i - left[i]-1) {
					dp[i] = dp[i - 1] + val[i] - val[i - 1];
				}
				else {
					if (left[i] - opt - 1 == i - left[i]-1) {
						if (opt-1>=L+(left[left[opt]-1]==0)&&dpmx[opt - 2] + gum(opt-1, i) <= dpmx[opt-1]+gum(opt,i)) {
							dp[i] = dpmx[opt - 2] + gum(opt - 1, i);
							opt--;
						}
						else {
							dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
						}

					}
					else {
						dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
					}
				}
			}
		}
		if (i != n - 1 && left[i + 1] != left[i]) {
			for (int r = i; r >= 0; r--) {
				if (r == i)dpmx[r] = dp[r];
				else if (dpmx[r] <= dpmx[r + 1] && dpmx[r] <= dp[r])break;
				else dpmx[r] = min(dp[r], dpmx[r + 1]);
			}
		}
	}
	int C;
	for (int i = 0; i < n; ++i) {
	//	cout << "dp["<<i<<"] = " << dp[i] << ":\n";
	}
	return dp[n-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:94:6: warning: unused variable 'C' [-Wunused-variable]
  int C;
      ^

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