Submission #73542

#	Time	Username	Problem	Language	Result	Execution time	Memory
73542		nvmdava	전선 연결 (IOI17_wiring)	C++17	0 / 100	3 ms	492 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define INF 2000000007
using namespace std;

struct Con{
	int x, c;
	Con(int _x, int _c){
		x = _x;
		c = _c;
	}
	bool operator<(const Con& rhs){
		return x < rhs.x;
	}
};

vector<Con> v;
long long ans[200005], lr[200005], lb[200005], s[200005];

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	v.push_back(Con(-INF, 0));
	v.push_back(Con(-INF, 1));
	
	for(auto x : r){
		v.push_back(Con(x, 0));
	}
	for(auto x : b){
		v.push_back(Con(x, 1));
	}
	sort(v.begin(), v.end());
	ans[0] = 0;
	ans[1] = 0;
	lr[0] = 0;
	lb[0] = 0;
	lr[1] = 1;
	lb[1] = 1;
	s[1] = -2 * INF;
	for(int i = 2; i < v.size(); i++){
		ans[i] = ans[i - 1];
		lr[i] = lr[i - 1];
		lb[i] = lb[i - 1];
		s[i] = s[i - 1] + v[i].x;
		if(v[i].c == 1){
			ans[i] += v[i].x - lr[i - 1];
			ans[i] = min(ans[i], ans[lr[i - 1] - 1] + s[i] - s[lr[i - 1] - 1] - v[lr[i - 1]].x * (i - lr[i - 1] + 1));
			lb[i] = i;
		} else {
			ans[i] += v[i].x - lb[i - 1];
			ans[i] = min(ans[i], ans[lb[i - 1] - 1] + s[i] - s[lb[i - 1] - 1] - v[lb[i - 1]].x * (i - lb[i - 1] + 1));
			lr[i] = i;
		}
	}
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:12: warning: integer overflow in expression [-Woverflow]
  s[1] = -2 * INF;
            ^
wiring.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < v.size(); i++){
                 ~~^~~~~~~~~~
wiring.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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