답안 #136810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136810 2019-07-26T10:10:50 Z antimirage Shortcut (IOI16_shortcut) C++14
컴파일 오류
0 ms 0 KB
#include "shortcut.h"
#include "grader.cpp"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 505;

int a[N], d[N], n;

long long suf[N], ans = 1e18, pos[N], inf = 1e18, calc[N][N], mx[N][N];

long long find_shortcut(int N, vector<int> qwe, vector<int> asd, int c) { n = N;
	for (int i = 0; i < n - 1; i++) {
		a[i] = asd[i];
		d[i] = qwe[i];
		if (i > 0) {
			pos[i] = pos[i - 1] + qwe[i - 1];
		}
	}
	pos[n - 1] = pos[n - 2] + qwe[n - 2];
	a[n - 1] = asd[n - 1];
	if (n == 2) {
		return min(c * 1ll, pos[1] - pos[0]) + a[0] + a[1];
	}
	for (int x = 0; x < n; x++) {
		mx[x][x] = pos[x] + a[x];
		for (int y = x + 1; y < n; y++) {
			mx[x][y] = max(mx[x][y - 1], pos[y] + a[y]);
		}
	}
	for (int x = 0; x < n; x++) {
		for (int y = x + 1; y < n; y++) {
			int j = x;
			for (int i = y; i >= x; i--) {
				suf[i] = max( (i == y ? 0 : suf[i + 1]), pos[y] - pos[i] + a[i]);
			}
			for (int i = x; i <= y; i++) {
				while (j <= y && pos[j] - pos[i] < pos[i] - pos[x] + pos[y] - pos[j] + c)
					j++;
				if (j > y)
					calc[x][y] = max(calc[x][y], mx[i][j - 1] - pos[i] + a[i]);
				else
					calc[x][y] = max(calc[x][y], max(suf[j] + pos[i] - pos[x] + a[i] + c, mx[i][j - 1] - pos[i] + a[i]));
			}
		}
	}
	for (int x = 0; x < n; x++) {
		for (int y = x + 1; y < n; y++) {
			long long mx1 = 0, mx2 = 0, res = calc[x][y];
			for (int i = 0; i <= x; i++) {
				mx1 = max(mx1, pos[x] - pos[i] + a[i]);
			}
			for (int i = y; i < n; i++) {
				mx2 = max(mx2, pos[i] - pos[y] + a[i]);
			}
			res = max(res, mx1 + mx2 + min(c * 1ll, pos[y] - pos[x]));
			for (int i = y; i >= x; i--) {
				res = max(res, min(c + pos[i] - pos[x], pos[y] - pos[i]) + mx2 + a[i]);
			}
			for (int i = x; i <= y; i++) {
				res = max(res, min(c + pos[y] - pos[i], pos[i] - pos[x]) + mx1 + a[i]);
			}
			ans = min(ans, res);
		}
	}
	return ans;
}

Compilation message

/tmp/cct1mJTX.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccYcHgVL.o:shortcut.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status