Submission #940903

#	Time	Username	Problem	Language	Result	Execution time	Memory
940903		beaboss	Wiring (IOI17_wiring)	C++14	0 / 100	172 ms	262144 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 = 1e15;

ll min_total_length(vector<int> r, vector<int> b) {
	vector<vi> dp;
	vector<vi> pref;

	ll n = r.size(), m = b.size();
	ll i, j;
	i = j = 0;

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

	while (i != n || j != m) {
		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()) {
		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].size() - 1; j >= 0; j--) {
			if (dp[i-1].size() - j - 1 >= 0) {
				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]));
			}
			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];


}

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

// 	ll res = min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10});
// 	cout << res << endl;
// }

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:35:7: warning: overflow in conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} changes value from '1000000000000000' to '-1530494976' [-Woverflow]
   35 |  r.pb(INF);
      |       ^~~
wiring.cpp:36:7: warning: overflow in conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} changes value from '1000000000000000' to '-1530494976' [-Woverflow]
   36 |  b.pb(INF);
      |       ^~~
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:54: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]
   54 |   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++)
......
   60 |  FOR(i, 1, dp.size()) {
      |      ~~~~~~~~~~~~~~~                    
wiring.cpp:60:2: note: in expansion of macro 'FOR'
   60 |  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++)
......
   62 |   FOR(j, 0, dp[i].size()) {
      |       ~~~~~~~~~~~~~~~~~~                
wiring.cpp:62:3: note: in expansion of macro 'FOR'
   62 |   FOR(j, 0, dp[i].size()) {
      |   ^~~

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