結果

問題 No.2304 Distinct Elements
ユーザー risujirohrisujiroh
提出日時 2023-05-12 22:56:53
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,297 bytes
コンパイル時間 3,719 ms
コンパイル使用メモリ 267,996 KB
実行使用メモリ 29,944 KB
最終ジャッジ日時 2024-11-28 19:36:23
合計ジャッジ時間 110,395 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
9,472 KB
testcase_02 AC 2 ms
9,472 KB
testcase_03 AC 2 ms
10,624 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 AC 76 ms
29,944 KB
testcase_10 AC 76 ms
28,536 KB
testcase_11 AC 75 ms
27,896 KB
testcase_12 AC 75 ms
29,820 KB
testcase_13 AC 75 ms
29,816 KB
testcase_14 AC 8 ms
8,960 KB
testcase_15 AC 3 ms
8,832 KB
testcase_16 AC 2 ms
10,624 KB
testcase_17 AC 2 ms
10,624 KB
testcase_18 AC 3 ms
9,344 KB
testcase_19 AC 2 ms
10,624 KB
testcase_20 AC 2 ms
9,344 KB
testcase_21 AC 2 ms
10,624 KB
testcase_22 AC 2 ms
9,216 KB
testcase_23 AC 2 ms
10,532 KB
testcase_24 AC 3 ms
8,832 KB
testcase_25 AC 3 ms
10,624 KB
testcase_26 AC 3 ms
9,600 KB
testcase_27 AC 2 ms
9,344 KB
testcase_28 AC 2 ms
10,624 KB
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 AC 61 ms
28,368 KB
testcase_33 AC 7 ms
10,624 KB
testcase_34 AC 63 ms
28,380 KB
testcase_35 AC 69 ms
29,864 KB
testcase_36 AC 6 ms
9,344 KB
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 TLE -
testcase_43 TLE -
testcase_44 AC 59 ms
28,312 KB
testcase_45 AC 43 ms
19,496 KB
testcase_46 AC 35 ms
23,160 KB
testcase_47 AC 10 ms
13,636 KB
testcase_48 AC 10 ms
10,624 KB
testcase_49 TLE -
testcase_50 TLE -
testcase_51 TLE -
testcase_52 TLE -
testcase_53 TLE -
testcase_54 TLE -
testcase_55 TLE -
testcase_56 TLE -
testcase_57 TLE -
testcase_58 TLE -
testcase_59 TLE -
testcase_60 AC 2 ms
5,248 KB
testcase_61 AC 2 ms
9,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#if __INCLUDE_LEVEL__ == 0
#include <bits/stdc++.h>
using namespace std;
#undef assert
#define assert(expr) (expr) || (__builtin_unreachable(), 0)
#include __BASE_FILE__
namespace std::ranges::views {
namespace {
struct S {
priority_queue<int> lower;
priority_queue<int, vector<int>, ::greater<>> upper;
explicit S(int x) { lower.push(x); }
int median() const { return lower.top(); }
void merge(S s) {
while (ssize(s.lower)) {
add(s.lower.top());
s.lower.pop();
}
while (ssize(s.upper)) {
add(s.upper.top());
s.upper.pop();
}
}
void add(int x) {
if (::empty(upper) || x < upper.top()) {
lower.push(x);
} else {
upper.push(x);
}
while (ssize(upper) < ssize(lower)) {
upper.push(lower.top());
lower.pop();
}
while (ssize(lower) < ssize(upper)) {
lower.push(upper.top());
upper.pop();
}
}
int64_t cost() {
int m = median();
int64_t cost = 0;
while (ssize(lower)) {
cost += abs(lower.top() - m);
lower.pop();
}
while (ssize(upper)) {
cost += abs(upper.top() - m);
upper.pop();
}
return cost;
}
};
void solve() {
int n;
cin >> n;
vector<int> a(n);
cin >> a;
sort(a);
for (int i : iota(0, n)) {
a[i] -= i;
}
vector<S> s;
for (int e : a) {
S t(e);
while (ssize(s) && t.median() < s.back().median()) {
t.merge(::move(s.back()));
s.pop_back();
}
s.push_back(t);
}
int64_t ans = 0;
for (auto&& e : s) {
ans += e.cost();
}
cout << ans << '\n';
}
} // namespace
} // namespace std::ranges::views
using views::solve;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
#else // __INCLUDE_LEVEL__
namespace std {
template <class T1, class T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
return is >> p.first >> p.second;
}
template <class... Ts>
istream& operator>>(istream& is, tuple<Ts...>& t) {
return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}
template <class R, enable_if_t<!is_convertible_v<R, string>>* = nullptr>
auto operator>>(istream& is, R&& r) -> decltype(is >> *begin(r)) {
for (auto&& e : r) {
is >> e;
}
return is;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << p.first << ' ' << p.second;
}
template <class... Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
auto f = [&os](const auto&... xs) -> ostream& {
[[maybe_unused]] auto sep = "";
((os << exchange(sep, " ") << xs), ...);
return os;
};
return apply(f, t);
}
namespace impl {
template <class R>
constexpr int n_dims(char) {
return 0;
}
template <class R>
constexpr auto n_dims(int) -> decltype(begin(declval<R>()), 0) {
return n_dims<decltype(*begin(declval<R>()))>(0) + 1;
}
} // namespace impl
template <class R, enable_if_t<!is_convertible_v<R, string_view>>* = nullptr>
auto operator<<(ostream& os, R&& r) -> decltype(os << *begin(r)) {
static constexpr int D = impl::n_dims<R>(0);
static const string SEP = 1 < D ? string(D - 1, '\n') : " ";
string sep;
for (auto&& e : r) {
os << exchange(sep, SEP) << e;
}
return os;
}
} // namespace std
#endif // __INCLUDE_LEVEL__
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0