Submission #739835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
739835	2023-05-11T11:32:24 Z	blue	Sparklers (JOI17_sparklers)	C++17	0 / 100	2000 ms	320 KB

sparklers

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvll = vector<vll>;
using vvi = vector<vi>;

#define sz(x) int(x.size())

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll N, K, T;
	cin >> N >> K >> T;

	vll X(1+N);
	for(int i = 1; i <= N; i++)
	{
		cin >> X[i];
	}



	ll lo = -1, hi = ((((1'000'000'000'000'000'000LL / 2LL + 1) / N) + 1) / T) + 1; 
	// ll lo = 1, hi = 1'000'000'000'000'000'000LL/N;
	while(lo != hi)
	{
		ll mid = (lo + hi)/2;

		vvll dp(1+N, vll(1+N, 0));

		// for(ll l = N; l >= 1; l--)
		for(ll l = K; l >= 1; l--)
		{
			for(ll r = K; r <= N; r++)
			{
				if(l == r)
					dp[l][r] = 1;
				else if(2LL * T * (r-l) * mid < X[r] - X[l])
				// else if(2LL * (r-l) * mid < X[r] - X[l])
					dp[l][r] = 0;
				else
					dp[l][r] = dp[l+1][r] || dp[l][r-1];
			}
		}

		if(dp[1][N] == 1)
			hi = mid;
		else
			lo = mid+1;
	}

	cout << lo << '\n';
}

Subtask #1

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Correct	1 ms	316 KB	Output is correct
19	Execution timed out	2090 ms	212 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Correct	1 ms	316 KB	Output is correct
19	Execution timed out	2090 ms	212 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Correct	1 ms	316 KB	Output is correct
19	Execution timed out	2090 ms	212 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-