답안 #46287 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46287	2018-04-18T19:05:42 Z	qoo2p5	Sparklers (JOI17_sparklers)	C++17	50 / 100	200 ms	50356 KB

sparklers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = 5005;

int n, k;
ll t;
ll x[N];
bool dp[N][N];

bool check(ll s) {
	memset(dp, 0, sizeof dp);
	dp[k][k] = 1;
	rep(len, 2, n + 1) {
		rep(l, 0, n) {
			int r = l + len - 1;
			if (r >= n) {
				break;
			}
			dp[l][r] = ((dp[l + 1][r] || dp[l][r - 1]) && (x[r] - x[l]) <= 2 * s * (r - l) * t);
		}
	}
	return dp[0][n - 1];
}

void run() {
	cin >> n >> k >> t;
	k--;
	rep(i, 0, n) {
		cin >> x[i];
	}
	ll left = -1;
	ll right = (x[n - 1] + t) / t;
	
	while (right - left > 1) {
		ll mid = (left + right) / 2;
		if (check(mid)) {
			right = mid;
		} else {
			left = mid;
		}
	}
	
	cout << right << "\n";
}

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	24952 KB	Output is correct
2	Correct	66 ms	25036 KB	Output is correct
3	Correct	93 ms	25036 KB	Output is correct
4	Correct	71 ms	25036 KB	Output is correct
5	Correct	78 ms	25036 KB	Output is correct
6	Correct	67 ms	25036 KB	Output is correct
7	Correct	80 ms	25088 KB	Output is correct
8	Correct	78 ms	25260 KB	Output is correct
9	Correct	87 ms	25260 KB	Output is correct
10	Correct	80 ms	25260 KB	Output is correct
11	Correct	71 ms	25280 KB	Output is correct
12	Correct	75 ms	25280 KB	Output is correct
13	Correct	79 ms	25280 KB	Output is correct
14	Correct	71 ms	25288 KB	Output is correct
15	Correct	72 ms	25288 KB	Output is correct
16	Correct	82 ms	25312 KB	Output is correct
17	Correct	75 ms	25312 KB	Output is correct
18	Correct	100 ms	25312 KB	Output is correct
19	Correct	18 ms	25312 KB	Output is correct
20	Correct	106 ms	25312 KB	Output is correct
21	Correct	19 ms	25312 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	24952 KB	Output is correct
2	Correct	66 ms	25036 KB	Output is correct
3	Correct	93 ms	25036 KB	Output is correct
4	Correct	71 ms	25036 KB	Output is correct
5	Correct	78 ms	25036 KB	Output is correct
6	Correct	67 ms	25036 KB	Output is correct
7	Correct	80 ms	25088 KB	Output is correct
8	Correct	78 ms	25260 KB	Output is correct
9	Correct	87 ms	25260 KB	Output is correct
10	Correct	80 ms	25260 KB	Output is correct
11	Correct	71 ms	25280 KB	Output is correct
12	Correct	75 ms	25280 KB	Output is correct
13	Correct	79 ms	25280 KB	Output is correct
14	Correct	71 ms	25288 KB	Output is correct
15	Correct	72 ms	25288 KB	Output is correct
16	Correct	82 ms	25312 KB	Output is correct
17	Correct	75 ms	25312 KB	Output is correct
18	Correct	100 ms	25312 KB	Output is correct
19	Correct	18 ms	25312 KB	Output is correct
20	Correct	106 ms	25312 KB	Output is correct
21	Correct	19 ms	25312 KB	Output is correct
22	Correct	132 ms	25312 KB	Output is correct
23	Correct	100 ms	25312 KB	Output is correct
24	Correct	95 ms	25312 KB	Output is correct
25	Correct	147 ms	25396 KB	Output is correct
26	Correct	159 ms	25424 KB	Output is correct
27	Correct	157 ms	25424 KB	Output is correct
28	Correct	158 ms	25424 KB	Output is correct
29	Correct	149 ms	25424 KB	Output is correct
30	Correct	161 ms	25424 KB	Output is correct
31	Correct	165 ms	25424 KB	Output is correct
32	Correct	154 ms	25472 KB	Output is correct
33	Correct	171 ms	25492 KB	Output is correct
34	Correct	177 ms	25492 KB	Output is correct
35	Correct	183 ms	25548 KB	Output is correct
36	Correct	155 ms	25548 KB	Output is correct
37	Correct	164 ms	25548 KB	Output is correct
38	Correct	178 ms	25548 KB	Output is correct
39	Correct	200 ms	25724 KB	Output is correct
40	Correct	20 ms	25724 KB	Output is correct

Subtask #3
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	24952 KB	Output is correct
2	Correct	66 ms	25036 KB	Output is correct
3	Correct	93 ms	25036 KB	Output is correct
4	Correct	71 ms	25036 KB	Output is correct
5	Correct	78 ms	25036 KB	Output is correct
6	Correct	67 ms	25036 KB	Output is correct
7	Correct	80 ms	25088 KB	Output is correct
8	Correct	78 ms	25260 KB	Output is correct
9	Correct	87 ms	25260 KB	Output is correct
10	Correct	80 ms	25260 KB	Output is correct
11	Correct	71 ms	25280 KB	Output is correct
12	Correct	75 ms	25280 KB	Output is correct
13	Correct	79 ms	25280 KB	Output is correct
14	Correct	71 ms	25288 KB	Output is correct
15	Correct	72 ms	25288 KB	Output is correct
16	Correct	82 ms	25312 KB	Output is correct
17	Correct	75 ms	25312 KB	Output is correct
18	Correct	100 ms	25312 KB	Output is correct
19	Correct	18 ms	25312 KB	Output is correct
20	Correct	106 ms	25312 KB	Output is correct
21	Correct	19 ms	25312 KB	Output is correct
22	Correct	132 ms	25312 KB	Output is correct
23	Correct	100 ms	25312 KB	Output is correct
24	Correct	95 ms	25312 KB	Output is correct
25	Correct	147 ms	25396 KB	Output is correct
26	Correct	159 ms	25424 KB	Output is correct
27	Correct	157 ms	25424 KB	Output is correct
28	Correct	158 ms	25424 KB	Output is correct
29	Correct	149 ms	25424 KB	Output is correct
30	Correct	161 ms	25424 KB	Output is correct
31	Correct	165 ms	25424 KB	Output is correct
32	Correct	154 ms	25472 KB	Output is correct
33	Correct	171 ms	25492 KB	Output is correct
34	Correct	177 ms	25492 KB	Output is correct
35	Correct	183 ms	25548 KB	Output is correct
36	Correct	155 ms	25548 KB	Output is correct
37	Correct	164 ms	25548 KB	Output is correct
38	Correct	178 ms	25548 KB	Output is correct
39	Correct	200 ms	25724 KB	Output is correct
40	Correct	20 ms	25724 KB	Output is correct
41	Runtime error	44 ms	50356 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

답안 #46287

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 50.0

Subtask #1
30.0 / 30.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 50.0