oj.uz

답안 #827165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827165 2023-08-16T09:31:54 Z tranxuanbach 전선 연결 (IOI17_wiring) C++17
0 / 100
 1000 ms 11148 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(const line_type& l){
		auto z = mts.insert(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){
		auto l = *mts.lower_bound(x);
		return l.a * x + l.b;
	}
};

int n, m;
bool col[N];

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

ll min_total_length(vector <int> r, vector <int> b){
	n = isz(r);
	m = isz(b);
	for (auto pos: r){
		col[pos] = true;
	}
	for (auto pos: b){
		col[pos] = false;
	}
	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;
		// cout << i << ' ' << pre[i][0].fi << ' ' << pre[i][0].se << ' ' << pre[i][1].fi << ' ' << pre[i][1].se << endl;
	}
	pref[0][0] = 0;
	pref[0][1] = 0;
	ForE(i, 1, n + m){
		pref[i][0] = pref[i - 1][0] + (col[i] == 0 ? i : 0);
		pref[i][1] = pref[i - 1][1] + (col[i] == 1 ? i : 0);
	}

	fill(dp, dp + n + m + 1, infll);
	dp[0] = 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], i - 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][col[i]] - pref[j][col[i]]) - (pref[j][col[i] ^ 1] - pref[j - leni][col[i] ^ 1]);
			for (int l = j - leni; l >= k; l--){
				dp[i] = min(dp[i], sum + dp[l]);
				sum += (j + 1) - l;
			}
		}
		// cout << i << ' ' << dp[i] << endl;
	}
	return dp[n + m];
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '25859', found: '1000000000000000007'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '904', found: '26'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '316', found: '36'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 550 ms 11140 KB Output is correct
3 Correct 21 ms 11084 KB Output is correct
4 Correct 67 ms 11148 KB Output is correct
5 Correct 25 ms 11064 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 308 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 312 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 1083 ms 11084 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '25859', found: '1000000000000000007'
2 Halted 0 ms 0 KB -