Submission #940919

#	Time	Username	Problem	Language	Result	Execution time	Memory
940919		beaboss	Wiring (IOI17_wiring)	C++14	100 / 100	33 ms	14156 KiB

wiring

// Source: https://oj.uz/problem/view/IOI17_wiring
// 
#include "wiring.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

const ll INF = 1e18;

ll min_total_length(vector<int> x, vector<int> y) {

	vi r;
	vi b;
	vector<vi> dp;
	vector<vi> pref;

	ll n = x.size(), m = y.size();
	FOR(i, 0 ,n) r.pb(x[i]);
	FOR(i, 0, m) b.pb(y[i]);
	ll i, j;
	i = j = 0;

	r.pb(INF);
	b.pb(INF);

	while (i != n || j != m) {
		// cout << i << j << endl;
		ll sz = 0;
		ll here=pref.size();
		pref.pb({0});
		if (r[i] < b[j]) {
			while (i != n && r[i] < b[j]) {
				pref[here].pb(r[i]);
				sz++;i++;
			}
		} else {
			while (j != m && b[j] < r[i]) {
				pref[here].pb(b[j]);
				sz++;j++;
			}
		}
		dp.pb(vi(sz+1, INF));
		assert(pref[here].size() == sz+1);
		FOR(i, 1, sz+1) pref[here][i] += pref[here][i-1];
	}

	dp[0][0] = 0;

	FOR(i, 1, dp.size()) {
		// cout << i << endl;
		ll best = INF;
		FOR(j, 0, dp[i].size()) {
			if ((ll) dp[i-1].size() - j - 1 >= 0) {
				// cout << 'd' << endl;
				// cout << best << endl;
				best = min(best, dp[i-1][dp[i-1].size() - j-1] - (pref[i-1][dp[i-1].size()-1] - pref[i-1][dp[i-1].size() - j-1]));
				// cout << best << endl;
				// cout << dp[i-1].size() - j-1 << endl;
			}
			// cout << i << j << ' ' << best << pref[i][j] << endl;
			ckmin(dp[i][j], best + pref[i][j]);
			best -= pref[i-1][pref[i-1].size() - 1] - pref[i-1][pref[i-1].size() - 2]; // get the last element from before
			// cout << ' ' << dp[i][j] << endl;
		}
		best = INF;
		for (ll j = dp[i-1].size() - 1; j >= 0; j--) {
			
			best = min(best, dp[i-1][dp[i-1].size() - j - 1] - (pref[i-1][dp[i-1].size()-1] - pref[i-1][dp[i-1].size() - j - 1]));
			
			// cout << best << endl;
			if (j < dp[i].size()) ckmin(dp[i][j], best + pref[i][j]);
			best += pref[i][1];
			// cout << i << j << ' ' << dp[i][j] << endl;
		}


	}

	return dp[dp.size()-1][dp[dp.size()-1].size()-1];


}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	ll res = min_total_length({0, 1, 2, 3}, {5, 6});
// 	cout << res << endl;
// }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from wiring.cpp:4:
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:60:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   60 |   assert(pref[here].size() == sz+1);
      |          ~~~~~~~~~~~~~~~~~~^~~~~~~
wiring.cpp:19:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (ll i = (a); i<b; i++)
......
   66 |  FOR(i, 1, dp.size()) {
      |      ~~~~~~~~~~~~~~~                    
wiring.cpp:66:2: note: in expansion of macro 'FOR'
   66 |  FOR(i, 1, dp.size()) {
      |  ^~~
wiring.cpp:19:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (ll i = (a); i<b; i++)
......
   69 |   FOR(j, 0, dp[i].size()) {
      |       ~~~~~~~~~~~~~~~~~~                
wiring.cpp:69:3: note: in expansion of macro 'FOR'
   69 |   FOR(j, 0, dp[i].size()) {
      |   ^~~
wiring.cpp:88:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    if (j < dp[i].size()) ckmin(dp[i][j], best + pref[i][j]);
      |        ~~^~~~~~~~~~~~~~

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