Submission #1036412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036412		beaconmc	Wiring (IOI17_wiring)	C++14	30 / 100	518 ms	115380 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
 
 
ll n,m;
vector<ll> R,B;
unordered_map<int,ll> cache;
unordered_map<int,ll> poses;
bool flag;
ll dp(ll x, ll y){
	if (flag && abs(poses[R[x]]-poses[B[y]]) > 20) return 1000000000000000;
	if (cache.count(x*1000000+y)) return cache[x*1000000+y];
	if (x==n && y==m) return 0;
	if (x>=n || y >= m) return 1000000000000000;
    
 
	return cache[x*1000000+y] = min(dp(x+1,y), min(dp(x,y+1), dp(x+1,y+1))) + abs(R[x] - B[y]);
}
 
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	if (r[r.size()-1] < b[0]){
		while (r.size() > b.size()){
			b.push_back(b[0]);
		}
		while (r.size() < b.size()){
			r.push_back(r[r.size()-1]);
		}
		ll sumr=0,sumb=0;
		for(auto&i : r) sumr += i;
		for (auto&i : b) sumb += i;
	 
		return sumb - sumr;
	}

	R.clear();
	B.clear();
	vector<ll> stuff;
	for (auto&i : r) stuff.push_back(i);
	for (auto&i : b) stuff.push_back(i);
	flag = false;
	if (r.size() > 200 || b.size() > 200) flag = true;
 
	sort(stuff.begin(), stuff.end());
	FOR(i,0,stuff.size()){
		poses[stuff[i]] = i;
	}
 
	cache.clear();
	for (auto&i : r) R.push_back(i);
	for (auto&i : b) B.push_back(i);
	n = r.size();
	m = b.size();
	return dp(0,0);
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:5:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   50 |  FOR(i,0,stuff.size()){
      |      ~~~~~~~~~~~~~~~~            
wiring.cpp:50:2: note: in expansion of macro 'FOR'
   50 |  FOR(i,0,stuff.size()){
      |  ^~~

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