Submission #24573

# Submission time Handle Problem Language Result Execution time Memory
24573 2017-06-10T13:14:48 Z gs14004 Shortcut (IOI16_shortcut) C++11
0 / 100
0 ms 17644 KB
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
int n, c;
lint a[1000005], b[1000005];

bool trial(lint x){
	lint ps = -1e18, pe = 1e18, ms = -1e18, me = 1e18;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(b[j] - b[i] + a[i] + a[j] > x){
				lint r = x - c - a[i] - a[j];
				ps = max(ps, b[i] + b[j] - r);
				pe = min(pe, b[i] + b[j] + r);
				ms = max(ms, b[i] - b[j] - r);
				me = min(me, b[i] + b[j] + r);
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			if(ps <= b[i] + b[j] && b[i] + b[j] <= pe &&
					ms <= b[i] - b[j] && b[i] - b[j] <= me){
				return 1;
			}
		}
	}
	return 0;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	::n = n;
	::c = c;
	for(int i=0; i<n; i++){
		a[i] = d[i];
		if(i >= 1) b[i] = b[i-1] + l[i-1];
	}
	lint s = 0, e = 1e16;
	while(s != e){
		lint m = (s+e)/2;
		if(trial(m)) e = m;
		else s = m+1;
	}
	return s;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB n = 4, 80 is a correct answer
2 Correct 0 ms 17644 KB n = 9, 110 is a correct answer
3 Correct 0 ms 17644 KB n = 4, 21 is a correct answer
4 Correct 0 ms 17644 KB n = 3, 4 is a correct answer
5 Correct 0 ms 17644 KB n = 2, 62 is a correct answer
6 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
7 Correct 0 ms 17644 KB n = 3, 29 is a correct answer
8 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
9 Correct 0 ms 17644 KB n = 2, 3 is a correct answer
10 Correct 0 ms 17644 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 17644 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 17644 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 17644 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 17644 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 17644 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 17644 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000318
18 Halted 0 ms 0 KB -