Submission #425952

#	Time	Username	Problem	Language	Result	Execution time	Memory
425952		arayi	Wiring (IOI17_wiring)	C++17	100 / 100	69 ms	8744 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long
#define ad push_back
#define MP make_pair
#define sc second
#define fr first

const int N = 1e6 + 30;
const lli mod = 1e17;
int n, m;
lli dp[N], sum[N];
vector<pair<int, int> > a;
lli s(int l, int r)
{
	lli ret = sum[r];
	if(l) ret -= sum[l - 1];
	return ret;
}
lli sm(int i1, int i2, int l)
{
	lli sum1 = s(i1, l), sum2 = s(l + 1, i2); 
	lli s1 = l-i1+1, s2=i2-l;
	if(s1 > s2)
		sum2 += (s1-s2) * a[l+1].fr;
	else
		sum1 += (s2-s1) * a[l].fr;
	sum2 -= sum1;
	if(i1 == 0) return sum2;
	return sum2 + min(dp[i1], dp[i1-1]);

}
long long min_total_length(vector<int> r, vector<int> b) 
{
	n=r.size(), m=b.size();
	for(auto p : r) a.ad(MP(p, 0));
	for(auto p : b) a.ad(MP(p, 1));
	sort(a.begin(), a.end());
	for (int i = 0; i < a.size(); i++)
	{
		sum[i]=a[i].fr;
		if(i) sum[i] += sum[i-1];
	}
	int i;
	for (i = 0; i < a.size(); i++)
	{
		dp[i] = mod;
		if(a[i].sc != a[i+1].sc) break;
	}
	int l = i, i1 = 0;
	i++;
	for (; i < a.size(); i++)
	{
		while (i1 > 0 && a[i1].sc == a[i1-1].sc)
		{
			if(sm(i1 - 1, i, l) < sm(i1, i, l)) i1--;
			else break;
		}
		dp[i] = sm(i1, i, l);
		if(i < a.size() - 1 && a[i].sc != a[i+1].sc) i1=l=i;
	}
	return dp[n + m - 1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
wiring.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (i = 0; i < a.size(); i++)
      |              ~~^~~~~~~~~~
wiring.cpp:53:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (; i < a.size(); i++)
      |         ~~^~~~~~~~~~
wiring.cpp:61:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   if(i < a.size() - 1 && a[i].sc != a[i+1].sc) i1=l=i;
      |      ~~^~~~~~~~~~~~~~

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