Submission #217056

#	Time	Username	Problem	Language	Result	Execution time	Memory
217056		davitmarg	Wiring (IOI17_wiring)	C++17	0 / 100	5 ms	384 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 = 100005;

vector<pair<LL, int>> a;
int n, last[2];
LL dp[N],pr[N][2];


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();
	a.PB(MP(0, 0));
	sort(all(a));


	for (int i = 1; i <= n; i++)
		dp[i] = mod * mod;

	last[0] = last[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		int col = a[i].second;
		LL pos = a[i].first;

		pr[i][0] = pr[i - 1][0];
		pr[i][1] = pr[i - 1][1];
		pr[i][col] += pos;

		last[col] = i;

		int lst = last[!col];
		if (!lst)
			continue;

		dp[i] = min(dp[i], dp[i - 1] + a[i].first - a[lst].first);
		dp[i] = min(dp[i], dp[lst - 1] + (pr[i][col]-pr[lst][col]) - (i - lst) * a[lst].first);
			
	}
	return dp[n];
}


#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


*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < r.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < b.size(); i++)
                  ~~^~~~~~~~~~

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