oj.uz

Submission #837294

# Submission time Handle Problem Language Result Execution time Memory
837294 2023-08-25T09:18:21 Z Johann Wiring (IOI17_wiring) C++14
13 / 100
 83 ms 15672 KB 
#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1LL << 60;

int N, M;
vi pos, color;
vi dp, intervals;

struct segtree
{
	int size;
	vi arr;
	void init(int _size)
	{
		size = 1;
		while (size < _size)
			size *= 2;
		arr.assign(2 * size, INF);
	}
	void set(int i, ll v)
	{
		i += size;
		arr[i] = v;
		while (i >>= 1 > 0)
			arr[i] = min(arr[2 * i], arr[2 * i + 1]);
	}
	ll query(int l, int r) { return query(l, r, 1, 0, size); }
	ll query(int l, int r, int x, int lx, int rx)
	{
		if (l <= lx && rx <= r)
			return arr[x];
		if (r <= lx || rx <= l)
			return INF;
		int m = (lx + rx) / 2;
		ll a = query(l, r, 2 * x, lx, m);
		ll b = query(l, r, 2 * x + 1, m, rx);
		return min(a, b);
	}
};
segtree segL; // compensation for gap will be done on the left
segtree segR; // compenstation for gap will be on the right <==> this is the pure naive cost

long long min_total_length(std::vector<int> _R, std::vector<int> _B)
{
	N = sz(_R), M = sz(_B);
	int ir = 0, ib = 0;
	while (ir + ib < N + M)
	{
		if (ir == N)
			color.push_back(1), pos.push_back(_B[ib++]);
		else if (ib == M)
			color.push_back(0), pos.push_back(_R[ir++]);
		else
		{
			if (_R[ir] < _B[ib])
				color.push_back(0), pos.push_back(_R[ir++]);
			else
				color.push_back(1), pos.push_back(_B[ib++]);
		}
	}

	int c = -1;
	for (int i = 0; i < sz(color); ++i)
	{
		if (c == color[i])
			continue;
		c = color[i];
		intervals.push_back(i);
	}
	intervals.push_back(sz(color)); // for the end of the last interval

	// init dp
	dp.assign(sz(pos) + 1, INF);
	segL.init(sz(dp));
	segR.init(sz(dp));
	dp[0] = 0; // cost of connection all stuff [0, i) only to the left
	{
		int l = 0, r = intervals[1];
		ll sum = (r - l) * pos[r] - accumulate(pos.begin(), pos.begin() + r, 0LL);
		segR.set(0, sum);
		sum -= (r - l) * (pos[r] - pos[r - 1]);
		segL.set(0, sum);
	}
	// do dp
	for (int j = 1, l, m, r; j < sz(intervals) - 1; ++j)
	{
		l = intervals[j - 1], m = intervals[j], r = intervals[j + 1];

		ll cost = 0;
		ll costComp = 0;
		for (int i = m; i < r; ++i)
		{
			cost += pos[i] - pos[m - 1];
			costComp += pos[i] - pos[m];
			ll tmp;
			tmp = segL.query(m - (i - m), m + 1);
			if (tmp != INF)
				dp[i + 1] = min(dp[i + 1], cost + tmp);
			tmp = segR.query(l, m - (i - m));
			if (tmp != INF)
				dp[i + 1] = min(dp[i + 1], costComp + tmp);
		}
		if (r < sz(pos))
		{
			cost = 0;
			costComp = 0;
			for (int i = r - 1; i >= m; --i)
			{
				if (dp[i + 1] != INF)
					segR.set(i + 1, dp[i + 1] + cost),
						segL.set(i + 1, dp[i + 1] + costComp);
				cost += pos[r] - pos[i];
				costComp += pos[r - 1] - pos[i];
			}
			if (dp[m] != INF)
				segR.set(m, dp[m] + cost),
					segL.set(m, dp[m] + costComp);
		}
	}

	return dp[N + M];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '3665', found: '3630'
5 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 37 ms 13380 KB Output is correct
4 Correct 31 ms 13360 KB Output is correct
5 Correct 36 ms 13496 KB Output is correct
6 Correct 45 ms 15016 KB Output is correct
7 Correct 44 ms 14904 KB Output is correct
8 Correct 50 ms 14904 KB Output is correct
9 Correct 45 ms 14904 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 83 ms 15672 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1051349362'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 76 ms 14904 KB 3rd lines differ - on the 1st token, expected: '373710605', found: '366140942'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '3665', found: '3630'
5 Halted 0 ms 0 KB -