結果

問題 No.919 You Are A Project Manager
ユーザー ooaiuooaiu
提出日時 2024-12-01 13:57:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 488 ms / 3,000 ms
コード長 3,420 bytes
コンパイル時間 3,505 ms
コンパイル使用メモリ 261,520 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2024-12-01 13:57:53
合計ジャッジ時間 13,510 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

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

#ifndef LOCAL
#include <bits/stdc++.h>
using namespace std;
#define debug(...) (void(0))
#else
#include "algo/debug.h"
#endif
template <class T>
struct MergeSortTree {
private:
int N;
int sz;
T mn, mx;
std::vector<std::vector<T>> dat;
int LB(const std::vector<T>& v, const T& x) const {
return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x));
}
public:
MergeSortTree() = default;
MergeSortTree(const std::vector<T>& v) : N((int)v.size()) {
mn = std::numeric_limits<T>::max();
mx = std::numeric_limits<T>::lowest();
sz = (int)std::bit_ceil((unsigned int)N);
dat.assign(2 * sz, {});
for (int i = 0; i < N; i++) {
dat[i + sz].push_back(v[i]);
mn = std::min(mn, v[i]);
mx = std::max(mx, v[i]);
}
for (int i = sz - 1; i >= 1; i--) {
dat[i].resize(dat[2 * i].size() + dat[2 * i + 1].size());
std::merge(dat[2 * i].begin(), dat[2 * i].end(), dat[2 * i + 1].begin(), dat[2 * i + 1].end(), dat[i].begin());
}
};
int count_lt(int l, int r, const T& x) const {
assert(0 <= l && l <= r && r <= N);
l += sz;
r += sz;
int ans = 0;
while (l < r) {
if (l & 1) ans += LB(dat[l++], x);
if (r & 1) ans += LB(dat[--r], x);
l >>= 1;
r >>= 1;
}
return ans;
}
int count_le(int l, int r, const T& x) const { return count_lt(l, r, x + 1); }
int count_gt(int l, int r, const T& x) const { return r - l - count_le(l, r, x); }
int count_ge(int l, int r, const T& x) const { return r - l - count_lt(l, r, x); }
T kth(int l, int r, const T& k) const {
T lo = mn, hi = mx + T{1};
while (hi > lo + 1) {
T mi = (lo + hi) >> 1;
(count_lt(l, r, mi) <= k ? lo : hi) = mi;
}
return lo;
}
};
#include <atcoder/segtree>
using S = int64_t;
S op(S a, S b) { return max(a, b); }
S e() { return -1e18; }
void solve() {
int N;
cin >> N;
vector<int> A(N), B(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
B[N - i - 1] = A[i];
}
MergeSortTree<int> A_freq(A);
MergeSortTree<int> B_freq(B);
constexpr S o = S(0);
int64_t ans = 0;
for (int K = 1; K <= N; K++) {
int sz = (N + K - 1) / K;
vector<int64_t> pref, suff;
pref.reserve(sz);
suff.reserve(sz);
{
int med = (K - 1) / 2;
for (int i = 0; i + K <= N; i += K) {
if (i == 0) {
pref.push_back(A_freq.kth(i, i + K, med));
suff.push_back(B_freq.kth(i, i + K, med));
} else {
pref.push_back(pref.back() + A_freq.kth(i, i + K, med));
suff.push_back(suff.back() + B_freq.kth(i, i + K, med));
}
}
}
atcoder::segtree<S, op, e> pp(pref), ss(suff);
for (unsigned i = 0; i <= pref.size(); i++) {
int64_t res = max(o, pp.prod(0, i)) + max(o, ss.prod(0, suff.size() - i));
if (res < 0) continue;
ans = max(ans, res * K);
}
}
cout << ans << endl;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt = 1;
// std::cin >> tt;
while (tt--) {
solve();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0