結果
問題 | No.919 You Are A Project Manager |
ユーザー |
|
提出日時 | 2019-10-26 00:11:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 3,000 ms |
コード長 | 2,639 bytes |
コンパイル時間 | 2,512 ms |
コンパイル使用メモリ | 190,020 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 17:36:48 |
合計ジャッジ時間 | 4,371 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 55 |
ソースコード
#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (n); i++)#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)#define rep2(i, l, r) for (int i = (l); i < (r); i++)#define rep2r(i, l, r) for (int i = (r) - 1; i >= (l); i--)#define range(a) a.begin(), a.end()using namespace std;using ll = long long;template<class T>struct wavelet_matrix {vector<int> dat;vector<vector<int>> cnt;vector<T> dic;wavelet_matrix(const vector<T> &a) : dat(a) {const int n = dat.size();dic.assign(a.begin(), a.end());sort(dic.begin(), dic.end());dic.erase(unique(dic.begin(), dic.end()), dic.end());for (int i = 0; i < n; i++) {dat[i] = lower_bound(dic.begin(), dic.end(), a[i]) - dic.begin();}int H = 1;while ((1 << H) < dic.size()) H++;cnt.resize(H, vector<int>(n + 1));auto dfs = [&](auto dfs, int l, int r, int h) -> void {if (r - l == 0) return;if (h == H) return;for (int i = l; i < r; i++) {cnt[h][i + 1] = cnt[h][i] + (~dat[i] >> (H - 1 - h) & 1);}int m = stable_partition(dat.begin() + l, dat.begin() + r, [&](T x) {return ~x >> (H - 1 - h) & 1;}) - dat.begin();dfs(dfs, l, m, h + 1);dfs(dfs, m, r, h + 1);};dfs(dfs, 0, n, 0);}T quantile(int l, int r, int k) {const int n = cnt[0].size() - 1;int a = 0;int b = n;for (int i = 0; i < cnt.size(); i++) {int cnt0 = cnt[i][b] - cnt[i][a];int c = cnt[i][r] - cnt[i][l];if (k < c) {l = a + cnt[i][l] - cnt[i][a];r = a + cnt[i][r] - cnt[i][a];b = a + cnt0;} else {l += cnt[i][b] - cnt[i][l];r += cnt[i][b] - cnt[i][r];k -= c;a += cnt0;}}return dic[dat[l]];}};int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(15);int N; cin >> N;vector<int> A(N); rep(i, N) cin >> A[i];wavelet_matrix<int> wm(A);ll ans = 0;for (int K = 1; K <= N; K++) {vector<ll> a, b;a.push_back(0);b.push_back(0);for (int i = 0; i + K <= N; i += K) {a.push_back(wm.quantile(i, i + K, (K - 1) / 2));}for (int i = N; i - K >= 0; i -= K) {b.push_back(wm.quantile(i - K, i, (K - 1) / 2));}rep(i, a.size() - 1) a[i + 1] += a[i];rep(i, b.size() - 1) b[i + 1] += b[i];rep(i, a.size() - 1) a[i + 1] = max(a[i + 1], a[i]);rep(i, b.size() - 1) b[i + 1] = max(b[i + 1], b[i]);for (int i = 0; i <= N / K; i++) {ans = max(ans, (a[i] + b[N / K - i]) * K);}}cout << ans << endl;}