Submission #310753

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
310753	2020-10-07T19:46:14 Z	mode149256	Swimming competition (LMIO18_plaukimo_varzybos)	C++17	100 / 100	494 ms	15044 KB

plaukimo_varzybos

/*input
5 2 4
1
3
3
1
4
*/
#include <bits/stdc++.h>
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;

int N, A, B;
vi sk;

int gali(int diff) {
	vi dp(N + 3, 0);

	dp[0] = 1;

	int j = 1;

	for (int i = 0; i < N; ++i)
	{
		if (i > 1) dp[i] += dp[i - 1];

		if (dp[i] <= 0) continue;

		j = max(j, i + 1);
		while (j + 1 <= N and sk[j + 1] - sk[i + 1] <= diff) j++;
		// printf("i = %d, j = %d, dp = %d, A = %d, B = %d, rib = %d %d\n", i, j, dp[i], A, B, i + A, min(i + B, j));

		if (i + A <= min(i + B, j)) {
			dp[i + A]++;
			dp[min(i + B, j) + 1]--;
		}
	}

	dp[N] += dp[N - 1];
	return dp[N] > 0;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// #ifndef LOCAL
// 	freopen("lmio_2018_3e2_plaukimo_varzybos_vyr.in", "r", stdin);
// 	freopen("lmio_2018_3e2_plaukimo_varzybos_vyr.out", "w", stdout);
// #endif

	cin >> N >> A >> B;
	sk = vi(N + 1);
	for (int i = 1; i <= N; ++i)
		cin >> sk[i];

	sort(sk.begin() + 1, sk.end());
	int l = 0;
	int h = 1e8;
	int m;
	while (l < h) {
		m = (l + h) / 2;

		// printf("m = %d, gali = %d\n", m, gali(m));
		if (gali(m))
			h = m;
		else
			l = m + 1;
	}

	printf("%d\n", l);
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	25 ms	1792 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	350 ms	15028 KB	Output is correct
5	Correct	308 ms	14900 KB	Output is correct
6	Correct	29 ms	1792 KB	Output is correct
7	Correct	273 ms	13512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct

Subtask #3
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	25 ms	1792 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	350 ms	15028 KB	Output is correct
5	Correct	308 ms	14900 KB	Output is correct
6	Correct	29 ms	1792 KB	Output is correct
7	Correct	273 ms	13512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	9 ms	768 KB	Output is correct
12	Correct	12 ms	896 KB	Output is correct
13	Correct	18 ms	1152 KB	Output is correct
14	Correct	44 ms	1536 KB	Output is correct
15	Correct	160 ms	8056 KB	Output is correct
16	Correct	389 ms	12024 KB	Output is correct
17	Correct	36 ms	1536 KB	Output is correct
18	Correct	19 ms	1280 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	488 ms	15028 KB	Output is correct
21	Correct	494 ms	15028 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	0 ms	384 KB	Output is correct
30	Correct	1 ms	384 KB	Output is correct
31	Correct	1 ms	384 KB	Output is correct

Subtask #4
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	25 ms	1792 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	350 ms	15028 KB	Output is correct
5	Correct	308 ms	14900 KB	Output is correct
6	Correct	29 ms	1792 KB	Output is correct
7	Correct	273 ms	13512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	9 ms	768 KB	Output is correct
12	Correct	12 ms	896 KB	Output is correct
13	Correct	18 ms	1152 KB	Output is correct
14	Correct	44 ms	1536 KB	Output is correct
15	Correct	160 ms	8056 KB	Output is correct
16	Correct	389 ms	12024 KB	Output is correct
17	Correct	36 ms	1536 KB	Output is correct
18	Correct	19 ms	1280 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	488 ms	15028 KB	Output is correct
21	Correct	494 ms	15028 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	0 ms	384 KB	Output is correct
30	Correct	1 ms	384 KB	Output is correct
31	Correct	1 ms	384 KB	Output is correct
32	Correct	14 ms	1032 KB	Output is correct
33	Correct	176 ms	7944 KB	Output is correct
34	Correct	159 ms	7928 KB	Output is correct
35	Correct	481 ms	14956 KB	Output is correct
36	Correct	339 ms	15044 KB	Output is correct
37	Correct	324 ms	14968 KB	Output is correct
38	Correct	205 ms	9524 KB	Output is correct

Submission #310753

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 30.0 / 30.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
30.0 / 30.0

Subtask #4
40.0 / 40.0