Submission #1063882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063882		pravcoder	Wiring (IOI17_wiring)	C++17	20 / 100	1095 ms	6236 KiB

wiring

	#include "wiring.h"
	#include <cmath>
	#include <cstdio>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	#include <string>
	using namespace std;

	typedef long long ll;
	typedef vector<int> vi;
	typedef vector<vi> v2i;
	typedef vector<ll> vl;
	typedef vector<vl> v2l;
	typedef pair<int, int> pi;
	typedef vector<pi> vpi;
	typedef vector<bool> vb;

	#define pb push_back
	#define mp make_pair
	#define rept(i, a, b) for (int i = a; i < b; i++)
	#define rep(i, n) for (int i = 0; i < n; i++)

	ll sub1(vi r, vi b) {
		int n = r.size(), m = b.size();
		//v2l dp(n, vl(m));
		vl dp1(m);
		vl dp2(m);
		dp1[0] = abs(r[0] - b[0]);
		rept(i, 1, m) {
			dp1[i] = dp1[i - 1] + abs(r[0] - b[i]);
		}
		rept(i, 1, n) {
			rep(j, m) {
				if (j == 0) {
					dp2[j] = dp1[j] + abs(r[i] - b[j]);
				}
				else {
					dp2[j] = min({ dp1[j], dp2[j - 1], dp1[j - 1] }) + abs(r[i] - b[j]);
				}
			}
			dp1 = dp2;
		}
		/*dp[0][0] = abs(r[0] - b[0]);
		rep(i, n) {
			rep(j, m) {
				if (max(i, j) > 0) {
					if (i == 0) {
						dp[i][j] = dp[i][j - 1] + abs(r[i] - b[j]);
					}
					else if (j == 0) {
						dp[i][j] = dp[i - 1][j] + abs(r[i] - b[j]);
					}
					else {
						dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + abs(r[i] - b[j]);
					}
				}
			}
		}*/
		return dp1[m - 1];
	}

	long long min_total_length(std::vector<int> r, std::vector<int> b) {
		int n = r.size(), m = b.size();
		if (r[n-1] >= b[0]) {
			return sub1(r, b);
		}
		ll length = 0;
		b.resize(max(m, n), b[0]);
		r.resize(max(m, n), r[n - 1]);
		rep(i, r.size()) length += b[i] - r[r.size() - i - 1];
		return length;
	}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:22:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  #define rep(i, n) for (int i = 0; i < n; i++)
......
   71 |   rep(i, r.size()) length += b[i] - r[r.size() - i - 1];
      |       ~~~~~~~~~~~                     
wiring.cpp:71:3: note: in expansion of macro 'rep'
   71 |   rep(i, r.size()) length += b[i] - r[r.size() - i - 1];
      |   ^~~

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