Submission #217071

#	Time	Username	Problem	Language	Result	Execution time	Memory
217071		davitmarg	Wiring (IOI17_wiring)	C++17	100 / 100	108 ms	22880 KiB

wiring

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()


#ifndef death
#include "wiring.h"
#endif // !death


using namespace std;

const int N = 200005;

vector<pair<LL, int>> a;
int n, k;
vector<vector<LL>> block, sf,pr,dp;

LL last(int i, int j)
{
	if (i+j == 0)
		return 0;
	if (j == 0)
		return dp[i - 1].back();
	return dp[i][j - 1];
}

LL min_total_length(vector<int> r, vector<int> b)
{
	for (int i = 0; i < r.size(); i++)
		a.push_back(MP(r[i], 0));
	for (int i = 0; i < b.size(); i++)
		a.push_back(MP(b[i], 1));
	n = r.size() + b.size();
	sort(all(a));
	for (int i = 0; i < n; i++)
	{
		if (!i || a[i].second != a[i - 1].second)
		{
			block.push_back(vector<LL>(0));
			sf.push_back(vector<LL>(0));
			pr.push_back(vector<LL>(0));
			dp.push_back(vector<LL>(0));
		}
		block.back().push_back(a[i].first);
	}

	k = block.size();
	for (int i = 0; i < k; i++)
	{
		LL dist;
		LL sum;

		dp[i].resize(block[i].size(), mod * mod);
		if (i)
		{
			sum = 0;
			dist = block[i][0] - block[i - 1].back();
			for (LL j = 0; j < block[i].size(); j++)
			{
				sum += block[i][j] - block[i][0];
				dp[i][j] = min(dp[i][j], sf[i - 1][max((int)sf[i - 1].size() - (int)j - 1,0)] + (j + 1ll) * dist + sum);
				if (j + 1 < block[i - 1].size())
					dp[i][j] = min(dp[i][j], pr[i - 1][pr[i - 1].size() - j - 2] + sum);
			}
		}

		if (i == k - 1)
			break;
		sum = 0;
		dist = block[i + 1][0] - block[i].back();

		sf[i].resize(block[i].size() + 1, mod * mod);
		pr[i].resize(block[i].size(), mod * mod);

		for (LL j = block[i].size() - 1; j >= 0; j--)
		{
			sum += block[i].back() - block[i][j];
			sf[i][j] = min(sf[i][j + 1], sum + min(last(i, j), dp[i][j]));
			pr[i][j] = sum + min(last(i, j), dp[i][j]) + (block[i].size() - j) * dist;
		}
		sf[i].pop_back();
		for (LL j = 1; j < block[i].size(); j++)
			pr[i][j] = min(pr[i][j], pr[i][j - 1]);

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


#ifdef death

int main()
{
	int X, Y;
	vector<int> x, y;
	cin >> X >> Y;
	while (X--)
	{
		x.push_back(0);
		cin >> x.back();
	}
	while (Y--)
	{
		y.push_back(0);
		cin >> y.back();
	}
	cout << "!!!! " << min_total_length(x, y) << endl;
	return 0;
}

#endif // death


/*
	
4 5
1 2 3 7
0 4 5 9 10

3 2
1 10 11
2 13

1 2
5
0 10

*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < r.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < b.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (LL j = 0; j < block[i].size(); j++)
                   ~~^~~~~~~~~~~~~~~~~
wiring.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j + 1 < block[i - 1].size())
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~
wiring.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (LL j = 1; j < block[i].size(); j++)
                  ~~^~~~~~~~~~~~~~~~~

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