제출 #54415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54415		aome	Shortcut (IOI16_shortcut)	C++17	71 / 100	1016 ms	4880 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 3005;
const long long INF = 1e18;

int n, c;
long long a[N];
long long b[N];

bool check(long long dis) {
	long long xmin, xmax, ymin, ymax;
	xmin = ymin = -INF, xmax = ymax = INF;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (i != j && abs(a[i] - a[j]) + b[i] + b[j] > dis) {
				long long x = a[i] + a[j];
				long long y = a[i] - a[j];
				if (dis < b[i] + b[j] + c) return 0;
				long long len = dis - c - b[i] - b[j];
				xmin = max(xmin, x - len);
				xmax = min(xmax, x + len);
				ymin = max(ymin, y - len);
				ymax = min(ymax, y + len);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			long long x = a[i] + a[j];
			long long y = a[i] - a[j];
			if (xmin <= x && x <= xmax && ymin <= y && y <= ymax) return 1;
		}
	}
	return 0;
}

long long find_shortcut(int _n, vector<int> l, vector<int> d, int _c) {
	n = _n, c = _c;
	for (int i = 1; i < n; ++i) {
		a[i] = a[i - 1] + l[i - 1];
	}
	for (int i = 0; i < n; ++i) b[i] = d[i];
	long long low = 0, high = 1e18;
	while (low < high) {
		long long mid = (low + high) >> 1;
		if (check(mid)) high = mid; else low = mid + 1;
	}
	return low;
}

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