oj.uz

Submission #136825

# Submission time Handle Problem Language Result Execution time Memory
136825 2019-07-26T10:25:50 Z antimirage Shortcut (IOI16_shortcut) C++14
0 / 100
 4 ms 376 KB 
#include "shortcut.h"
#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];
	for (int x = 0; x < n; x++) {
		mx[x][x] = pos[x] + a[x];
		mx[x + 1][x] = -inf;
		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++) {
			for (int i = y; i >= x; i--) {
				suf[i] = max( (i == y ? 0 : suf[i + 1]), pos[y] - pos[i] + a[i]);
			}
			int j = x + 1;
			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 (x == 1 && y == 2)
				//	cout << j << endl;
				if (j > y)
					calc[x][y] = max(calc[x][y], mx[i + 1][y] - pos[i] + a[i]);
				else
					calc[x][y] = max(calc[x][y], max(mx[i + 1][j - 1] - pos[i] + a[i], c + suf[j] + a[i] + pos[i] - pos[x]));
			}
		}
	}
	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;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 376 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 376 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -