Submission #130922

#	Time	Username	Problem	Language	Result	Execution time	Memory
130922		Adhyyan1252	Wiring (IOI17_wiring)	C++11	17 / 100	1082 ms	11768 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define cerr if(false) cerr
const int INF = 1e17;
struct segtree{

	vector<int> t;
	int sz; 

	segtree(int size){
		sz = size;
		t = vector<int>(sz*4, INF);
	}

	void upd(int i, int s, int e, int indx, int val){
		if(s == e){
			t[i] = val;
			return;
		}
		int m = (s + e)/2;
		if(indx <= m) upd(i*2, s, m, indx, val);
		else upd(i*2+1, m+1, e, indx, val);
		t[i] = min(t[i*2], t[i*2+1]);
	}

	int query(int i, int s, int e, int l, int r){
		if(l <= s && e <= r) return t[i];
		if(s > r || e < l || s > e) return INF;
		int m = (s + e)/2;
		return min(query(i*2, s, m, l, r), query(i*2+1, m+1, e, l, r));
	}

	void upd(int indx, int val){
		upd(1, 0, sz-1, indx, val);
	}

	int query(int l, int r){
		return query(1, 0, sz-1, l, r);
	}
};



long long min_total_length(std::vector<signed> r, std::vector<signed> b) {
	int n = r.size(), m = b.size();
	vector<pair<int, int> > a(n+m);
	for(int i = 0; i < n; i++) a[i] = {r[i], 0};
	for(int i = 0; i < m; i++) a[i+n]= {b[i], 1};

	sort(a.begin(), a.end());
	
	vector<int> prev(n+m), next(n+m);
	prev[0] = 0;
	for(int i = 1; i < a.size(); i++){
		if(a[i].second == a[i-1].second){
			prev[i] = prev[i-1];
		}else{
			prev[i] = i;
		}
	}
	next[n+m-1] = n+m-1;
	for(int i = n + m - 2; i >= 0; i--){
		if(a[i].second == a[i+1].second){
			next[i] = next[i+1];
		}else{
			next[i] = i;
		}
	}

	for(int i = 0; i < n+m; i++){
		cerr<<i<<": "<<a[i].first<<" "<<a[i].second<<" "<<prev[i]<<" "<<next[i]<<endl;
	}

	vector<int> dp(n+m);
	for(int i = 0; i <= next[0]; i++){
		dp[i] = INF;
	}
	
	for(int i = next[0]+1; i < n+m; i++){
			
		// int j = prev[i];
		// int sumR = 0;
		// for(int k = j; k <= i; k++){
		// 	sumR += a[k].first;
		// }
		// int ans = INF;
		// int sumL = 0;
		// int dR = (i - j + 1);	
		// for(int k = j-1; k >= prev[j-1]; k--){
		// 	int dL = (j - k);
		// 	sumL += a[k].first;
		// 	int cost = (k == 0?0:dp[k-1]);
		// 	cost += (a[j-1].first*dL - sumL);
		// 	cost += (sumR - a[j].first*dR);
		// 	cost += max(d1, d2)
		// }


		int j = prev[i];
		int d1 = (i - j + 1);
		int ans = INF;
		int sumA = 0, sumB = 0;
		for(int k = i; k >= j; k--){
			sumA += a[k].first;
		}
		for(int k = j-1; k >= prev[j-1]; k--){
			sumB += a[k].first;
			int d2 = (j - k);
			int cost = min((k?dp[k-1]:0), dp[k]) + (max(d1, d2)*(a[j].first - a[j-1].first)) + (a[j-1].first*d2 - sumB) + (sumA - a[j].first*d1);
			ans = min(ans, cost);
		}
		dp[i] = ans;
		cerr<<"DP "<<i<<" "<<dp[i]<<endl;

		cerr<<"DP "<<i<<" "<<dp[i]<<endl;
	}

	return dp[n+m-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < a.size(); i++){
                 ~~^~~~~~~~~~

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