oj.uz

Submission #136817

# Submission time Handle Problem Language Result Execution time Memory
136817 2019-07-26T10:15:48 Z antimirage Shortcut (IOI16_shortcut) C++14
0 / 100
 2 ms 376 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];
	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++) {
				calc[x][y] = max(calc[x][y], min(mx[i + 1][y] - pos[i] + a[i], c + suf[i + 1] + 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;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:37:8: warning: unused variable 'j' [-Wunused-variable]
    int j = x;
        ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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