oj.uz

Submission #1053197

# Submission time Handle Problem Language Result Execution time Memory
1053197 2024-08-11T09:38:15 Z pawned Wiring (IOI17_wiring) C++17
0 / 100
 0 ms 600 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
 
#include "wiring.h"
 
ll min_total_length(vector<int> r_g, vector<int> b_g) {
	vi r, b;
	for (int x : r_g)
		r.pb(x);
	for (int x : b_g)
		b.pb(x);
	int N = r.size();
	int M = b.size();
	vector<ii> vals;
	for (int i = 0; i < N; i++) {
		vals.pb({r[i], 0});
	}
	for (int i = 0; i < M; i++) {
		vals.pb({b[i], 1});
	}
	vals.pb({-1e9, -1});
	sort(vals.begin(), vals.end());
/*	cout<<"vals: ";
	for (ii p : vals)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	int K = N + M;
	vals[0].se = 1 - vals[1].se;	// opposite start as placeholder

	vi pfs(K + 1, 0);
	for (int i = 1; i <= K; i++) {
		pfs[i] = pfs[i - 1] + vals[i].fi;
	}
/*	cout<<"pfs: ";
	for (ll x : pfs)
		cout<<x<<" ";
	cout<<endl;*/
	vi dp(K + 1, 0);
	ll prev = 1;
	for (ll i = 1; i <= K; i++) {	// i = start of comp
		ll j = i;	// j = end of comp
		while (j < K && vals[j].se == vals[j + 1].se)
			j++;
		ll minv = dp[i - 1];
		ll sum = 0;	// total connection cost to i - 1
		for (int k = i; k <= j; k++) {
			sum += (vals[k].fi - vals[i - 1].fi);
			ll vc = 2 * i - k - 1;	// paired (vc, k), (vc + 1, k - 1), up to (i - 1, i)
			if (vc >= prev) {
				ll toadd = vals[i - 1].fi * (i - vc) + (pfs[vc - 1] - pfs[i - 1]);
				// toadd: extra connection cost from pairing w/ vc, vc+1, ... instead of all w/ i-1
				minv = min(minv, dp[vc - 1] + toadd);
			}
			dp[k] = minv + sum;
		}
		prev = i;
		i = j;
	}
	return dp[K];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14522'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '904', found: '5000000682'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB 3rd lines differ - on the 1st token, expected: '27', found: '30'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14522'
3 Halted 0 ms 0 KB -