結果
| 問題 | No.919 You Are A Project Manager |
| ユーザー |
 monnu
|
| 提出日時 | 2024-02-05 07:16:32 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 45 ms / 3,000 ms |
| コード長 | 9,768 bytes |
| コンパイル時間 | 2,367 ms |
| コンパイル使用メモリ | 191,176 KB |
| 実行使用メモリ | 7,680 KB |
| 最終ジャッジ日時 | 2024-09-28 11:31:35 |
| 合計ジャッジ時間 | 5,132 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 55 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define INF (1000000000000000000)template <class T>class WaveletMatrix{int BIT_SIZE = 0;T unit;vector<int> _a;vector<T> order;vector<vector<int>> _B;vector<vector<T>> _sum;vector<T> _finalSum;vector<vector<int>> _rank1;vector<vector<int>> _select0;vector<vector<int>> _select1;vector<int> _zeroCount;vector<int> _start, _last;int range_freq_internal(int s, int e, int low, int high, int b){if (s > e){return 0;}if (b == -1){return e - s + 1;}if (low == 0 && high == ((1 << (b + 1)) - 1)){return e - s + 1;}if (((low >> b) & 1) == 1){int _s = _zeroCount[b] + _rank1[b][s - 1] + 1;int _e = _zeroCount[b] + _rank1[b][e];return range_freq_internal(_s, _e, low ^ (1 << b), high ^ (1 << b), b - 1);}if (((high >> b) & 1) == 0){int _s = (s - 1) - _rank1[b][s - 1] + 1;int _e = e - _rank1[b][e];return range_freq_internal(_s, _e, low, high, b - 1);}int x, y;{int _s = (s - 1) - _rank1[b][s - 1] + 1;int _e = e - _rank1[b][e];x = range_freq_internal(_s, _e, low, (1 << b) - 1, b - 1);}{int _s = _zeroCount[b] + _rank1[b][s - 1] + 1;int _e = _zeroCount[b] + _rank1[b][e];y = range_freq_internal(_s, _e, 0, high ^ (1 << b), b - 1);}return x + y;}T range_sum_internal(int s, int e, int low, int high, int b){if (s > e){return unit;}if (b == -1){if (s == 0){return _finalSum[e];}else{return _finalSum[e] - _finalSum[s - 1];}}if (low == 0 && high == ((1 << (b + 1)) - 1)){if (s == 0){return _sum[b][e];}else{return _sum[b][e] - _sum[b][s - 1];}}if (((low >> b) & 1) == 1){int _s = _zeroCount[b] + _rank1[b][s - 1] + 1;int _e = _zeroCount[b] + _rank1[b][e];return range_sum_internal(_s, _e, low ^ (1 << b), high ^ (1 << b), b - 1);}if (((high >> b) & 1) == 0){int _s = (s - 1) - _rank1[b][s - 1] + 1;int _e = e - _rank1[b][e];return range_sum_internal(_s, _e, low, high, b - 1);}T x, y;{int _s = (s - 1) - _rank1[b][s - 1] + 1;int _e = e - _rank1[b][e];x = range_sum_internal(_s, _e, low, (1 << b) - 1, b - 1);}{int _s = _zeroCount[b] + _rank1[b][s - 1] + 1;int _e = _zeroCount[b] + _rank1[b][e];y = range_sum_internal(_s, _e, 0, high ^ (1 << b), b - 1);}return x + y;}public:WaveletMatrix(vector<T> A, T _unit) : unit(_unit){int N = A.size();for (int i = 0; i < N; i++){order.push_back(A[i]);}sort(order.begin(), order.end());order.erase(unique(order.begin(), order.end()), order.end());while ((1 << BIT_SIZE) < order.size()){BIT_SIZE++;}vector<int> a(N);for (int i = 0; i < N; i++){int k = lower_bound(order.begin(), order.end(), A[i]) - order.begin();a[i] = k;}_B.resize(BIT_SIZE);_sum.resize(BIT_SIZE);_rank1.resize(BIT_SIZE);_select0.resize(BIT_SIZE);_select1.resize(BIT_SIZE);_zeroCount.resize(BIT_SIZE, 0);for (int b = BIT_SIZE - 1; b >= 0; b--){vector<int> a_tmp[2];_B[b].push_back(-1);_sum[b].push_back(unit);_rank1[b].push_back(0);_select0[b].push_back(-1);_select1[b].push_back(-1);for (int i = 0; i < N; i++){int f = (a[i] >> b) & 1;_B[b].push_back(f);_sum[b].push_back(_sum[b].back() + order[a[i]]);_rank1[b].push_back(_rank1[b].back() + f);if (f == 0){_select0[b].push_back(i + 1);}else{_select1[b].push_back(i + 1);}a_tmp[f].push_back(a[i]);}a.clear();for (int x : a_tmp[0]){a.push_back(x);}for (int x : a_tmp[1]){a.push_back(x);}_zeroCount[b] = a_tmp[0].size();}_start = vector<int>(order.size(), -1);_last = vector<int>(order.size(), -1);for (int i = (int)a.size() - 1; i >= 0; i--){_start[a[i]] = i + 1;}for (int i = 0; i < a.size(); i++){_last[a[i]] = i + 1;}_finalSum.push_back(unit);for (int i = 0; i < N; i++){_finalSum.push_back(_finalSum.back() + order[a[i]]);}_a = a;}T access(int i){int ret = 0;for (int b = BIT_SIZE - 1; b >= 0; b--){if (_B[b][i] == 0){i = i - _rank1[b][i];}else{ret += (1 << b);i = _zeroCount[b] + _rank1[b][i];}}return order[ret];}int rank(T x, int i){int num = lower_bound(order.begin(), order.end(), x) - order.begin();if (num >= order.size() || order[num] != x){return 0;}for (int b = BIT_SIZE - 1; b >= 0; b--){if (((num >> b) & 1) == 0){i = i - _rank1[b][i];if (i == 0){return 0;}}else{if (_rank1[b][i] == 0){return 0;}i = _zeroCount[b] + _rank1[b][i];}}return i - _start[num] + 1;}int select(T x, int ith){if (ith == 0){return -1;}int num = lower_bound(order.begin(), order.end(), x) - order.begin();if (num >= order.size() || order[num] != x){return -1;}if (_last[num] - _start[num] + 1 < ith){return -1;}ith = _start[num] + (ith - 1);for (int b = 0; b < BIT_SIZE; b++){if (((num >> b) & 1) == 0){ith = _select0[b][ith];}else{ith = _select1[b][ith - _zeroCount[b]];}}return ith;}T quantile(int s, int e, int r){for (int b = BIT_SIZE - 1; b >= 0; b--){int cnt = (e - _rank1[b][e]) - ((s - 1) - _rank1[b][s - 1]);if (cnt >= r){s = (s - 1) - _rank1[b][s - 1] + 1;e = e - _rank1[b][e];}else{r -= cnt;s = _zeroCount[b] + _rank1[b][s - 1] + 1;e = _zeroCount[b] + _rank1[b][e];}}int num = _a[s - 1];return order[num];}int range_freq(int s, int e, T low, T high){if (s > e){return 0;}int l = lower_bound(order.begin(), order.end(), low) - order.begin();int r = upper_bound(order.begin(), order.end(), high) - order.begin();r--;if (l > r){return 0;}return range_freq_internal(s, e, l, r, BIT_SIZE - 1);}T range_sum(int s, int e, T low, T high){if (s > e){return 0;}int l = lower_bound(order.begin(), order.end(), low) - order.begin();int r = upper_bound(order.begin(), order.end(), high) - order.begin();r--;if (l > r){return 0;}return range_sum_internal(s, e, l, r, BIT_SIZE - 1);}};int main(){int N;cin >> N;vector<ll> A(N);for (int i = 0; i < N; i++){cin >> A[i];}WaveletMatrix<ll> wm(A, 0);ll ans = 0;for (int K = 1; K <= N; K++){vector<ll> sum1, sum2;sum1.push_back(0);sum2.push_back(0);for (int i = 1; i + K - 1 <= N; i += K){sum1.push_back(wm.quantile(i, i + K - 1, (K + 1) / 2) * K);}for (int i = N - K + 1; i > 0; i -= K){sum2.push_back(wm.quantile(i, i + K - 1, (K + 1) / 2) * K);}for (int i = 1; i < sum1.size(); i++){sum1[i] += sum1[i - 1];}for (int i = 1; i < sum2.size(); i++){sum2[i] += sum2[i - 1];}for (int i = 1; i < sum2.size(); i++){sum2[i] = max(sum2[i], sum2[i - 1]);}for (int i = 0; i < sum1.size(); i++){ans = max(ans, sum1[i] + sum2[N / K - i]);}}cout << ans << endl;}