oj.uz

Submission #827248

# Submission time Handle Problem Language Result Execution time Memory
827248 2023-08-16T10:09:38 Z tranxuanbach Wiring (IOI17_wiring) C++17
55 / 100
 1000 ms 237108 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())

using ll = long long;

const ll infll = (ll)1e18 + 7;

const int N = 2e5 + 5;

struct line_container{
	struct line_type{
		ll a, b;
		mutable ll p;
		bool operator< (const line_type& oth) const{
			return a < oth.a;
		}
		bool operator< (ll x) const{
			return p < x;
		}
	};

	multiset <line_type, less<>> mts;
	const ll inf = infll;

	ll div(ll x, ll y){
		return x / y - ((x ^ y) < 0 and x % y);
	}

	template <class T>
	bool isect(T x, T y){
		if (y == mts.end()){
			x->p = infll;
			return false;
		}
		if (x->a == y->a){
			x->p = x->b > y->b ? infll : -infll;
		}
		else{
			x->p = div(y->b - x->b, x->a - y->a);
		}
		return x->p >= y->p;
	}

	void insert(line_type l){
		l.a = -l.a; l.b = -l.b;
		auto z = mts.insert(mts.end(), l), y = z++, x = y;
		while (isect(y, z)){
			z = mts.erase(z);
		}
		if (x != mts.begin() and isect(--x, y)){
			isect(x, mts.erase(y));
		}
		while ((y = x) != mts.begin() and (--x)->p >= y->p){
			isect(x, mts.erase(y));
		}
	}

	ll query(ll x){
		if (mts.empty()){
			return infll;
		}
		auto l = *mts.lower_bound(x);
		return -(l.a * x + l.b);
	}
};

int n, m;
int a[N];
bool col[N];

pair <int, int> pre[N][2];
ll pref[N];
ll dp[N];

line_container seg[1 << 19];

void update(int id, int l, int r, int i, const line_container::line_type& ln){
	seg[id].insert(ln);
	if (l == r){
		return;
	}
	int mid = (l + r) >> 1;
	if (i <= mid){
		update(id * 2, l, mid, i, ln);
	}
	else{
		update(id * 2 + 1, mid + 1, r, i, ln);
	}
}

ll query(int id, int l, int r, int u, int v, ll x){
	if (v < l or r < u){
		return infll;
	}
	if (u <= l and r <= v){
		return seg[id].query(x);
	}
	int mid = (l + r) >> 1;
	return min(query(id * 2, l, mid, u, v, x), query(id * 2 + 1, mid + 1, r, u, v, x));
}

void update_dp(int i){
	update(1, 0, n + m, i, line_container::line_type{i, dp[i] + pref[i]});
}

ll min_total_length(vector <int> r, vector <int> b){
	n = isz(r);
	m = isz(b);
	{
		int i = 0, j = 0;
		while (i < n or j < m){
			if (j == m){
				a[i + j + 1] = r[i];
				col[i + j + 1] = true;
				i++;
			}
			else if (i == n){
				a[i + j + 1] = b[j];
				col[i + j + 1] = false;
				j++;
			}
			else if (r[i] < b[j]){
				a[i + j + 1] = r[i];
				col[i + j + 1] = true;
				i++;
			}
			else{
				a[i + j + 1] = b[j];
				col[i + j + 1] = false;
				j++;
			}
		}
	}
	pre[0][0] = pair{0, 0};
	pre[0][1] = pair{0, 0};
	ForE(i, 1, n + m){
		pre[i][0] = pre[i - 1][0];
		pre[i][1] = pre[i - 1][1];
		swap(pre[i][col[i]].fi, pre[i][col[i]].se);
		pre[i][col[i]].fi = i;
	}
	pref[0] = 0;
	ForE(i, 1, n + m){
		pref[i] = pref[i - 1] + a[i];
	}

	fill(dp, dp + n + m + 1, infll);
	dp[0] = 0;
	update_dp(0);
	ForE(i, 1, n + m){
		if (pre[i][0].fi == 0 or pre[i][1].fi == 0){
			continue;
		}
		int j = pre[i][col[i] ^ 1].fi;
		dp[i] = min(dp[i], a[i] - a[j] + dp[i - 1]);
		int k = pre[j][col[i]].fi;
		int leni = i - j, lenj = j - k;
		if (leni <= lenj){
			ll sum = (pref[i] - pref[j]) - (pref[j] - pref[j - leni]);
			int r = j - leni, l = k;
			// cout << l << ' ' << r << ' ' << query(1, 0, n + m, l, r, -(j + 1)) << endl;
			dp[i] = min(dp[i], sum + (ll)r * a[j + 1] - pref[r] + query(1, 0, n + m, l, r, -a[j + 1]));
			// for (int x = j - leni; x >= k; x--){
			// 	dp[i] = min(dp[i], sum + dp[x]);
			// 	sum += (j + 1) - x;
			// }
		}
		// cout << "dp " << i << ' ' << dp[i] << endl;
		update_dp(i);
	}
	return dp[n + m];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29012 KB Output is correct
2 Correct 14 ms 29036 KB Output is correct
3 Correct 14 ms 28972 KB Output is correct
4 Correct 14 ms 29020 KB Output is correct
5 Correct 13 ms 29000 KB Output is correct
6 Correct 14 ms 29012 KB Output is correct
7 Correct 15 ms 29164 KB Output is correct
8 Correct 15 ms 29140 KB Output is correct
9 Correct 14 ms 29140 KB Output is correct
10 Correct 15 ms 29248 KB Output is correct
11 Correct 14 ms 29140 KB Output is correct
12 Correct 14 ms 29284 KB Output is correct
13 Correct 15 ms 29168 KB Output is correct
14 Correct 15 ms 29168 KB Output is correct
15 Correct 15 ms 29164 KB Output is correct
16 Correct 14 ms 29288 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29012 KB Output is correct
2 Correct 15 ms 29032 KB Output is correct
3 Correct 264 ms 94252 KB Output is correct
4 Correct 256 ms 94212 KB Output is correct
5 Correct 503 ms 151380 KB Output is correct
6 Correct 531 ms 156712 KB Output is correct
7 Correct 506 ms 156680 KB Output is correct
8 Correct 517 ms 156688 KB Output is correct
9 Correct 503 ms 156784 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29012 KB Output is correct
2 Correct 16 ms 29032 KB Output is correct
3 Correct 783 ms 190168 KB Output is correct
4 Correct 752 ms 185676 KB Output is correct
5 Correct 15 ms 29012 KB Output is correct
6 Correct 15 ms 29036 KB Output is correct
7 Correct 14 ms 29036 KB Output is correct
8 Correct 14 ms 29032 KB Output is correct
9 Correct 17 ms 29068 KB Output is correct
10 Correct 17 ms 29164 KB Output is correct
11 Correct 15 ms 29076 KB Output is correct
12 Correct 14 ms 29060 KB Output is correct
13 Correct 16 ms 29060 KB Output is correct
14 Correct 14 ms 29040 KB Output is correct
15 Correct 14 ms 29040 KB Output is correct
16 Correct 14 ms 29036 KB Output is correct
17 Correct 15 ms 29032 KB Output is correct
18 Correct 775 ms 189920 KB Output is correct
19 Correct 766 ms 189812 KB Output is correct
20 Correct 765 ms 186244 KB Output is correct
21 Correct 784 ms 189840 KB Output is correct
22 Correct 766 ms 188364 KB Output is correct
23 Correct 750 ms 188536 KB Output is correct
24 Correct 764 ms 188832 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29012 KB Output is correct
2 Correct 935 ms 230740 KB Output is correct
3 Correct 736 ms 182636 KB Output is correct
4 Correct 883 ms 213648 KB Output is correct
5 Correct 770 ms 182640 KB Output is correct
6 Correct 14 ms 29012 KB Output is correct
7 Correct 14 ms 29016 KB Output is correct
8 Correct 14 ms 29032 KB Output is correct
9 Correct 14 ms 29012 KB Output is correct
10 Correct 14 ms 29036 KB Output is correct
11 Correct 14 ms 28972 KB Output is correct
12 Correct 14 ms 29012 KB Output is correct
13 Correct 14 ms 29012 KB Output is correct
14 Correct 14 ms 29012 KB Output is correct
15 Correct 15 ms 29140 KB Output is correct
16 Correct 14 ms 29028 KB Output is correct
17 Correct 16 ms 29048 KB Output is correct
18 Correct 845 ms 207912 KB Output is correct
19 Correct 859 ms 209352 KB Output is correct
20 Correct 944 ms 219184 KB Output is correct
21 Correct 973 ms 224928 KB Output is correct
22 Correct 767 ms 193140 KB Output is correct
23 Correct 617 ms 162860 KB Output is correct
24 Correct 748 ms 185872 KB Output is correct

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29012 KB Output is correct
2 Correct 14 ms 29036 KB Output is correct
3 Correct 14 ms 28972 KB Output is correct
4 Correct 14 ms 29020 KB Output is correct
5 Correct 13 ms 29000 KB Output is correct
6 Correct 14 ms 29012 KB Output is correct
7 Correct 15 ms 29164 KB Output is correct
8 Correct 15 ms 29140 KB Output is correct
9 Correct 14 ms 29140 KB Output is correct
10 Correct 15 ms 29248 KB Output is correct
11 Correct 14 ms 29140 KB Output is correct
12 Correct 14 ms 29284 KB Output is correct
13 Correct 15 ms 29168 KB Output is correct
14 Correct 15 ms 29168 KB Output is correct
15 Correct 15 ms 29164 KB Output is correct
16 Correct 14 ms 29288 KB Output is correct
17 Correct 14 ms 29012 KB Output is correct
18 Correct 15 ms 29032 KB Output is correct
19 Correct 264 ms 94252 KB Output is correct
20 Correct 256 ms 94212 KB Output is correct
21 Correct 503 ms 151380 KB Output is correct
22 Correct 531 ms 156712 KB Output is correct
23 Correct 506 ms 156680 KB Output is correct
24 Correct 517 ms 156688 KB Output is correct
25 Correct 503 ms 156784 KB Output is correct
26 Correct 14 ms 29012 KB Output is correct
27 Correct 16 ms 29032 KB Output is correct
28 Correct 783 ms 190168 KB Output is correct
29 Correct 752 ms 185676 KB Output is correct
30 Correct 15 ms 29012 KB Output is correct
31 Correct 15 ms 29036 KB Output is correct
32 Correct 14 ms 29036 KB Output is correct
33 Correct 14 ms 29032 KB Output is correct
34 Correct 17 ms 29068 KB Output is correct
35 Correct 17 ms 29164 KB Output is correct
36 Correct 15 ms 29076 KB Output is correct
37 Correct 14 ms 29060 KB Output is correct
38 Correct 16 ms 29060 KB Output is correct
39 Correct 14 ms 29040 KB Output is correct
40 Correct 14 ms 29040 KB Output is correct
41 Correct 14 ms 29036 KB Output is correct
42 Correct 15 ms 29032 KB Output is correct
43 Correct 775 ms 189920 KB Output is correct
44 Correct 766 ms 189812 KB Output is correct
45 Correct 765 ms 186244 KB Output is correct
46 Correct 784 ms 189840 KB Output is correct
47 Correct 766 ms 188364 KB Output is correct
48 Correct 750 ms 188536 KB Output is correct
49 Correct 764 ms 188832 KB Output is correct
50 Correct 14 ms 29012 KB Output is correct
51 Correct 935 ms 230740 KB Output is correct
52 Correct 736 ms 182636 KB Output is correct
53 Correct 883 ms 213648 KB Output is correct
54 Correct 770 ms 182640 KB Output is correct
55 Correct 14 ms 29012 KB Output is correct
56 Correct 14 ms 29016 KB Output is correct
57 Correct 14 ms 29032 KB Output is correct
58 Correct 14 ms 29012 KB Output is correct
59 Correct 14 ms 29036 KB Output is correct
60 Correct 14 ms 28972 KB Output is correct
61 Correct 14 ms 29012 KB Output is correct
62 Correct 14 ms 29012 KB Output is correct
63 Correct 14 ms 29012 KB Output is correct
64 Correct 15 ms 29140 KB Output is correct
65 Correct 14 ms 29028 KB Output is correct
66 Correct 16 ms 29048 KB Output is correct
67 Correct 845 ms 207912 KB Output is correct
68 Correct 859 ms 209352 KB Output is correct
69 Correct 944 ms 219184 KB Output is correct
70 Correct 973 ms 224928 KB Output is correct
71 Correct 767 ms 193140 KB Output is correct
72 Correct 617 ms 162860 KB Output is correct
73 Correct 748 ms 185872 KB Output is correct
74 Correct 566 ms 159368 KB Output is correct
75 Correct 781 ms 199280 KB Output is correct
76 Correct 667 ms 177484 KB Output is correct
77 Correct 934 ms 228448 KB Output is correct
78 Correct 742 ms 191532 KB Output is correct
79 Execution timed out 1000 ms 237108 KB Time limit exceeded
80 Halted 0 ms 0 KB -