結果
問題 | No.919 You Are A Project Manager |
ユーザー |
|
提出日時 | 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 |
ソースコード
#ifndef LOCAL#include <bits/stdc++.h>using namespace std;#define debug(...) (void(0))#else#include "algo/debug.h"#endiftemplate <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();}}