#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma region dalykai
template <typename F>
void _debug(F f)
{
f();
}
#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion
using change_t = vector<vector<pair<int, bool>>>;
void fix_multisets(int i,
change_t &insert, change_t &erase,
multiset<int> &opt, multiset<int> &diff)
{
for (auto &[val, which] : insert[i])
{
if (which)
{
opt.insert(val);
}
else
{
diff.insert(val);
}
}
for (auto &[val, which] : erase[i])
{
if (which)
{
auto it = opt.find(val);
opt.erase(it);
}
else
{
auto it = diff.find(val);
diff.erase(it);
}
}
}
int main()
{
#ifndef _AAAAAAAAA
// freopen("lmio_2018_3e2_plaukimo_varzybos_vyr.in", "r", stdin);
// freopen("lmio_2018_3e2_plaukimo_varzybos_vyr.out", "w", stdout);
// ios_base::sync_with_stdio(false);
// cin.tie(0);
#else
freopen("swim.in", "r", stdin);
#ifndef __linux__
atexit([]()
{
freopen("con", "r", stdin);
system("pause"); });
#endif
#endif
int n, l, u;
cin >> n >> l >> u;
vi32 nums(n);
for (int i = 0; i < n; i++)
{
cin >> nums[i];
}
sort(nums.begin(), nums.end());
vi32 dp(n, INT_MAX);
vvp32 change(n + 1);
// true jei is opt
vector<vector<pair<int, bool>>> erase(n + 1), insert(n + 1);
multiset<int> opt, diff;
insert[min(n, l - 1)].emplace_back(nums[0], false);
erase[min(n, u)].emplace_back(nums[0], false);
fix_multisets(0, insert, erase, opt, diff);
// kazkaip reikia pradzia (i = 0) sutvarkyt
for (int i = 1; i < n; i++)
{
fix_multisets(i, insert, erase, opt, diff);
if (opt.size())
{
dp[i] = min(dp[i], *opt.begin());
}
if (diff.size())
{
dp[i] = min(dp[i], nums[i] - *diff.rbegin());
}
if (i >= n - 1 || dp[i] == INT_MAX)
{
continue;
}
int bound = dp[i] + nums[i + 1];
int lower = min(n, i + l);
int upper = min(n, i + u);
if (lower == n)
{
continue;
}
bound = (int)distance(nums.begin(), upper_bound(nums.begin(), nums.end(), bound));
if (bound < lower)
{
insert[min(n, lower)].emplace_back(nums[i + 1], false);
erase[min(n, upper + 1)].emplace_back(nums[i + 1], false);
continue;
}
insert[lower].emplace_back(dp[i], true);
if (bound > upper)
{
erase[min(n, upper + 1)].emplace_back(dp[i], true);
}
else
{
erase[bound].emplace_back(dp[i], true);
insert[bound].emplace_back(nums[i + 1], false);
erase[min(n, upper + 1)].emplace_back(nums[i + 1], false);
}
}
debug([&]()
{
for (auto &a : dp)
{
cout << a << ' ';
}
cout << '\n';
//
});
cout << dp.back() << '\n';
return 0;
}
Compilation message
plaukimo_varzybos.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
8 | #pragma region dalykai
|
plaukimo_varzybos.cpp:45: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
45 | #pragma endregion
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
39 ms |
8780 KB |
Output is correct |
3 |
Correct |
7 ms |
1336 KB |
Output is correct |
4 |
Correct |
448 ms |
100956 KB |
Output is correct |
5 |
Correct |
420 ms |
85432 KB |
Output is correct |
6 |
Correct |
44 ms |
10824 KB |
Output is correct |
7 |
Correct |
355 ms |
76952 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 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 |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 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 |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
39 ms |
8780 KB |
Output is correct |
3 |
Correct |
7 ms |
1336 KB |
Output is correct |
4 |
Correct |
448 ms |
100956 KB |
Output is correct |
5 |
Correct |
420 ms |
85432 KB |
Output is correct |
6 |
Correct |
44 ms |
10824 KB |
Output is correct |
7 |
Correct |
355 ms |
76952 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 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 |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
22 ms |
4936 KB |
Output is correct |
22 |
Correct |
20 ms |
7440 KB |
Output is correct |
23 |
Correct |
40 ms |
10564 KB |
Output is correct |
24 |
Correct |
50 ms |
12104 KB |
Output is correct |
25 |
Correct |
289 ms |
100936 KB |
Output is correct |
26 |
Correct |
553 ms |
121468 KB |
Output is correct |
27 |
Correct |
61 ms |
12996 KB |
Output is correct |
28 |
Correct |
39 ms |
10748 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
861 ms |
160936 KB |
Output is correct |
31 |
Correct |
864 ms |
161084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
39 ms |
8780 KB |
Output is correct |
3 |
Correct |
7 ms |
1336 KB |
Output is correct |
4 |
Correct |
448 ms |
100956 KB |
Output is correct |
5 |
Correct |
420 ms |
85432 KB |
Output is correct |
6 |
Correct |
44 ms |
10824 KB |
Output is correct |
7 |
Correct |
355 ms |
76952 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
22 ms |
4936 KB |
Output is correct |
12 |
Correct |
20 ms |
7440 KB |
Output is correct |
13 |
Correct |
40 ms |
10564 KB |
Output is correct |
14 |
Correct |
50 ms |
12104 KB |
Output is correct |
15 |
Correct |
289 ms |
100936 KB |
Output is correct |
16 |
Correct |
553 ms |
121468 KB |
Output is correct |
17 |
Correct |
61 ms |
12996 KB |
Output is correct |
18 |
Correct |
39 ms |
10748 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
861 ms |
160936 KB |
Output is correct |
21 |
Correct |
864 ms |
161084 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
35 ms |
9540 KB |
Output is correct |
33 |
Correct |
497 ms |
83624 KB |
Output is correct |
34 |
Correct |
395 ms |
90440 KB |
Output is correct |
35 |
Correct |
963 ms |
178360 KB |
Output is correct |
36 |
Correct |
1243 ms |
159612 KB |
Output is correct |
37 |
Correct |
656 ms |
117324 KB |
Output is correct |
38 |
Correct |
554 ms |
115668 KB |
Output is correct |