답안 #46288 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46288	2018-04-18T19:15:53 Z	qoo2p5	Sparklers (JOI17_sparklers)	C++17	50 / 100	206 ms	49788 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], a[N];
bool dp[N][N];

bool check(ll s) {
	memset(dp, 0, sizeof dp);
	dp[k][k] = 1;
	rep(i, 0, n) {
		a[i] = x[i] - 2 * s * t * i;
	}
	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]) && a[l] >= a[r]);
		}
	}
	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	62 ms	24824 KB	Output is correct
2	Correct	71 ms	25064 KB	Output is correct
3	Correct	70 ms	25064 KB	Output is correct
4	Correct	87 ms	25064 KB	Output is correct
5	Correct	79 ms	25064 KB	Output is correct
6	Correct	85 ms	25064 KB	Output is correct
7	Correct	71 ms	25064 KB	Output is correct
8	Correct	89 ms	25064 KB	Output is correct
9	Correct	107 ms	25064 KB	Output is correct
10	Correct	92 ms	25184 KB	Output is correct
11	Correct	65 ms	25184 KB	Output is correct
12	Correct	82 ms	25184 KB	Output is correct
13	Correct	84 ms	25184 KB	Output is correct
14	Correct	67 ms	25184 KB	Output is correct
15	Correct	66 ms	25184 KB	Output is correct
16	Correct	72 ms	25188 KB	Output is correct
17	Correct	80 ms	25188 KB	Output is correct
18	Correct	80 ms	25188 KB	Output is correct
19	Correct	19 ms	25188 KB	Output is correct
20	Correct	85 ms	25188 KB	Output is correct
21	Correct	18 ms	25188 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	24824 KB	Output is correct
2	Correct	71 ms	25064 KB	Output is correct
3	Correct	70 ms	25064 KB	Output is correct
4	Correct	87 ms	25064 KB	Output is correct
5	Correct	79 ms	25064 KB	Output is correct
6	Correct	85 ms	25064 KB	Output is correct
7	Correct	71 ms	25064 KB	Output is correct
8	Correct	89 ms	25064 KB	Output is correct
9	Correct	107 ms	25064 KB	Output is correct
10	Correct	92 ms	25184 KB	Output is correct
11	Correct	65 ms	25184 KB	Output is correct
12	Correct	82 ms	25184 KB	Output is correct
13	Correct	84 ms	25184 KB	Output is correct
14	Correct	67 ms	25184 KB	Output is correct
15	Correct	66 ms	25184 KB	Output is correct
16	Correct	72 ms	25188 KB	Output is correct
17	Correct	80 ms	25188 KB	Output is correct
18	Correct	80 ms	25188 KB	Output is correct
19	Correct	19 ms	25188 KB	Output is correct
20	Correct	85 ms	25188 KB	Output is correct
21	Correct	18 ms	25188 KB	Output is correct
22	Correct	111 ms	25196 KB	Output is correct
23	Correct	112 ms	25196 KB	Output is correct
24	Correct	102 ms	25196 KB	Output is correct
25	Correct	164 ms	25256 KB	Output is correct
26	Correct	164 ms	25256 KB	Output is correct
27	Correct	166 ms	25256 KB	Output is correct
28	Correct	176 ms	25256 KB	Output is correct
29	Correct	170 ms	25256 KB	Output is correct
30	Correct	161 ms	25256 KB	Output is correct
31	Correct	203 ms	25256 KB	Output is correct
32	Correct	167 ms	25256 KB	Output is correct
33	Correct	172 ms	25256 KB	Output is correct
34	Correct	201 ms	25256 KB	Output is correct
35	Correct	196 ms	25256 KB	Output is correct
36	Correct	206 ms	25256 KB	Output is correct
37	Correct	173 ms	25256 KB	Output is correct
38	Correct	188 ms	25256 KB	Output is correct
39	Correct	192 ms	25256 KB	Output is correct
40	Correct	20 ms	25256 KB	Output is correct

Subtask #3
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	24824 KB	Output is correct
2	Correct	71 ms	25064 KB	Output is correct
3	Correct	70 ms	25064 KB	Output is correct
4	Correct	87 ms	25064 KB	Output is correct
5	Correct	79 ms	25064 KB	Output is correct
6	Correct	85 ms	25064 KB	Output is correct
7	Correct	71 ms	25064 KB	Output is correct
8	Correct	89 ms	25064 KB	Output is correct
9	Correct	107 ms	25064 KB	Output is correct
10	Correct	92 ms	25184 KB	Output is correct
11	Correct	65 ms	25184 KB	Output is correct
12	Correct	82 ms	25184 KB	Output is correct
13	Correct	84 ms	25184 KB	Output is correct
14	Correct	67 ms	25184 KB	Output is correct
15	Correct	66 ms	25184 KB	Output is correct
16	Correct	72 ms	25188 KB	Output is correct
17	Correct	80 ms	25188 KB	Output is correct
18	Correct	80 ms	25188 KB	Output is correct
19	Correct	19 ms	25188 KB	Output is correct
20	Correct	85 ms	25188 KB	Output is correct
21	Correct	18 ms	25188 KB	Output is correct
22	Correct	111 ms	25196 KB	Output is correct
23	Correct	112 ms	25196 KB	Output is correct
24	Correct	102 ms	25196 KB	Output is correct
25	Correct	164 ms	25256 KB	Output is correct
26	Correct	164 ms	25256 KB	Output is correct
27	Correct	166 ms	25256 KB	Output is correct
28	Correct	176 ms	25256 KB	Output is correct
29	Correct	170 ms	25256 KB	Output is correct
30	Correct	161 ms	25256 KB	Output is correct
31	Correct	203 ms	25256 KB	Output is correct
32	Correct	167 ms	25256 KB	Output is correct
33	Correct	172 ms	25256 KB	Output is correct
34	Correct	201 ms	25256 KB	Output is correct
35	Correct	196 ms	25256 KB	Output is correct
36	Correct	206 ms	25256 KB	Output is correct
37	Correct	173 ms	25256 KB	Output is correct
38	Correct	188 ms	25256 KB	Output is correct
39	Correct	192 ms	25256 KB	Output is correct
40	Correct	20 ms	25256 KB	Output is correct
41	Runtime error	43 ms	49788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

답안 #46288

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