Submission #59357

#	Time	Username	Problem	Language	Result	Execution time	Memory
59357		ekrem	Wiring (IOI17_wiring)	C++98	100 / 100	119 ms	75236 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000000000007
#define N 1000005
using namespace std;
typedef long long ll;
typedef vector < ll > vi;
typedef pair < ll , ll > ii;

ll n, m, l1, r1, l2, r2, pre[N];
ii a[N], b[N];
ll dp[N];

ll f(int n, int m){
	ll &r = dp[n];
	if(r != -1)
		return r;
	return r;
}

ll min_total_length(vector < int > r, vector < int > bb) {
	for(int i = 0; i < r.size(); i++)a[++n] = mp(r[i], 1);
	for(int i = 0; i < bb.size(); i++)a[++n] = mp(bb[i], 0);
	sort(a + 1, a + n + 1);

	for(int i = 1; i <= n; i++)
		pre[i] = pre[i - 1] + a[i].st;

	for(int i = 1; i <= n; i++){
		int j = i + 1;
		while(j <= n and a[j].nd == a[j - 1].nd)
			j++;
		b[++m] = mp(i, j - 1);
		// cout << i << " " << j - 1 << endl;
		i = j - 1;
	}

	if(m == 1)return 0;

	for(ll i = 1; i <= b[1].nd; i++)
		dp[i] = i*a[b[2].st].st - pre[i];

	for(ll j = 2; j <= m; j++){
		l1 = b[j - 1].st;
		r1 = b[j - 1].nd;
		l2 = b[j].st;
		r2 = b[j].nd;
		for(ll i = l2; i <= r2; i++){
			dp[i] = inf;
			if(i - l2 + 1 <= r1 - l1 + 1){
				dp[i] = dp[r1 - (i - l2 + 1)] + (pre[i] - pre[l2 - 1]) - (pre[r1] - pre[r1 - (i - l2 + 1)]);
			}
			if(j + 1 <= m)
				dp[i] = min(dp[i], dp[i - 1] + (a[b[j + 1].st].st - a[i].st));
			dp[i] = min(dp[i], dp[i - 1] + (a[i].st - a[b[j - 1].nd].st));
				// cout << i << " " << dp[i] << endl;
		}
	}

	return dp[n];
}


// int main() {
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	int n, m;
// 	assert(2 == scanf("%d %d", &n, &m));
// 	vector<int> r(n), b(m);
// 	for(int i = 0; i < n; i++)
// 		assert(1 == scanf("%d", &r[i]));
// 	for(int i = 0; i < m; i++)
// 		assert(1 == scanf("%d", &b[i]));

// 	ll res = min_total_length(r, b);
// 	printf("%lld\n", res);

// 	return 0;
// }

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < r.size(); i++)a[++n] = mp(r[i], 1);
                 ~~^~~~~~~~~~
wiring.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < bb.size(); i++)a[++n] = mp(bb[i], 0);
                 ~~^~~~~~~~~~~

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