제출 #827177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827177		caganyanmaz	Shortcut (IOI16_shortcut)	C++11	0 / 100	0 ms	212 KiB

shortcut

#include <bits/stdc++.h>

#define pb push_back
#define int int64_t
#include "shortcut.h"

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
using namespace std;

constexpr static int MXN = 255;
constexpr static int INF = 1e16;
int pf[MXN];
vector<int> d;
int c;

static inline int get_dist(int a, int b)
{
	return pf[max(a,b)] - pf[min(a,b)];
}

static inline int get_real_dist(int a, int b, int l, int r) // a <= b
{
	if (a > b) swap(a, b);
	return d[a] + d[b] + min(get_dist(a, b), get_dist(a, l) + get_dist(b, r) + c);
}

long long find_shortcut(int32_t n, vector<int32_t> _l, vector<int32_t> _d, int32_t _c)
{
	for (int i : _d)
		d.pb(i);
	c = _c;
	for (int i = 1; i < n; i++)
		pf[i] = pf[i-1] + static_cast<int>(_l[i-1]);
	int mn = 0;
	for (int i = 0; i < n; i++)
		for (int j = i; j < n; j++)
			mn = max(mn, get_dist(i, j) + d[i] + d[j]);
	debug(mn);
	for (int l = 0; l < n; l++)
	{
		for (int r = l+1; r < n; r++)
		{
			int mx = 0;
			for (int i = 0; i < n; i++)
				for (int j = i; j < n; j++)
					mx = max(mx, get_real_dist(i, j, l, r));
			mn = min(mn, mx);
			debug(l, r, mx);
		}
	}
	return mn;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3