Submission #1035417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035417		0npata	Wiring (IOI17_wiring)	C++17	17 / 100	1087 ms	12292 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector
#define int long long

const int INF = 1e18;

long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
	vec<vec<int>> v(0);

	int n = r.size();
	int m = b.size();

	int lst = -1;
	{
	int i = 0;
	int j = 0;
	while(i+j < n+m) {
		if(i == n || (j<m && b[j] < r[i])) {
			if(lst != 0) {
				lst = 0;
				v.push_back({});
			}
			v.back().push_back(b[j]);
			j++;
		}
		else {
			if(lst != 1) {
				lst = 1;
				v.push_back({});
			}
			v.back().push_back(r[i]); i++; }
	}
	}



	vec<vec<int>> dp(v.size());
	dp[0] = vec<int>(v[0].size()+1, INF);
	dp[0][0] = 0;

	for(int i = 1; i<v.size(); i++) {
		dp[i] = vec<int>(v[i].size()+1, INF);

		int k = v[i-1].size()-1;

		dp[i][0] = dp[i-1].back();
		int asum = 0;
		int bsum = v[i-1][k];


		for(int j = 1; j<=v[i].size(); j++) {
			auto eval = [&]() {
				int psz = v[i-1].size()-k;
				return (asum - bsum) + max(j - psz, 0ll) * (-v[i-1].back()) + max(psz - j, 0ll) * v[i][0] + min(dp[i-1][k], dp[i-1][k+1]);
			};

			asum += v[i][j-1];

			k = v[i-1].size();
			bsum = 0;

			while(k > 0) {
				//int cur = eval();
				k--;
				bsum += v[i-1][k];
				int cur = 0;
				dp[i][j] = min(dp[i][j], eval());
				//cerr << eval() << ' ';
				int nxt = eval();
				if(nxt > cur && i > 1 && false) {
					bsum -= v[i-1][k];
					k++;
					break;
				}
			}
			//cerr << '\n';

			//dp[i][j] = eval();
			//cerr << k << ' '  << dp[i][j] << ' ';
		}
		//cerr << '\n';
	}



	return dp.back().back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:45:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 1; i<v.size(); i++) {
      |                 ~^~~~~~~~~
wiring.cpp:55:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j = 1; j<=v[i].size(); j++) {
      |                  ~^~~~~~~~~~~~~

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