結果
問題 | No.919 You Are A Project Manager |
ユーザー | fine |
提出日時 | 2019-11-08 03:38:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 592 ms / 3,000 ms |
コード長 | 4,601 bytes |
コンパイル時間 | 2,015 ms |
コンパイル使用メモリ | 180,984 KB |
実行使用メモリ | 9,036 KB |
最終ジャッジ日時 | 2023-09-10 03:51:59 |
合計ジャッジ時間 | 15,219 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 498 ms
8,840 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 41 ms
4,380 KB |
testcase_05 | AC | 45 ms
4,376 KB |
testcase_06 | AC | 4 ms
4,380 KB |
testcase_07 | AC | 155 ms
5,344 KB |
testcase_08 | AC | 24 ms
4,380 KB |
testcase_09 | AC | 16 ms
4,376 KB |
testcase_10 | AC | 34 ms
4,376 KB |
testcase_11 | AC | 32 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 43 ms
4,380 KB |
testcase_14 | AC | 3 ms
4,380 KB |
testcase_15 | AC | 10 ms
4,376 KB |
testcase_16 | AC | 68 ms
4,560 KB |
testcase_17 | AC | 329 ms
8,620 KB |
testcase_18 | AC | 330 ms
8,716 KB |
testcase_19 | AC | 496 ms
9,036 KB |
testcase_20 | AC | 518 ms
8,188 KB |
testcase_21 | AC | 495 ms
8,988 KB |
testcase_22 | AC | 175 ms
5,668 KB |
testcase_23 | AC | 171 ms
5,612 KB |
testcase_24 | AC | 186 ms
5,472 KB |
testcase_25 | AC | 172 ms
5,612 KB |
testcase_26 | AC | 492 ms
8,032 KB |
testcase_27 | AC | 413 ms
7,504 KB |
testcase_28 | AC | 569 ms
8,596 KB |
testcase_29 | AC | 328 ms
8,580 KB |
testcase_30 | AC | 327 ms
8,724 KB |
testcase_31 | AC | 314 ms
8,724 KB |
testcase_32 | AC | 325 ms
8,652 KB |
testcase_33 | AC | 194 ms
5,724 KB |
testcase_34 | AC | 195 ms
5,736 KB |
testcase_35 | AC | 589 ms
8,648 KB |
testcase_36 | AC | 592 ms
8,708 KB |
testcase_37 | AC | 587 ms
8,576 KB |
testcase_38 | AC | 586 ms
8,760 KB |
testcase_39 | AC | 2 ms
4,380 KB |
testcase_40 | AC | 10 ms
4,380 KB |
testcase_41 | AC | 3 ms
4,380 KB |
testcase_42 | AC | 4 ms
4,376 KB |
testcase_43 | AC | 6 ms
4,380 KB |
testcase_44 | AC | 15 ms
4,376 KB |
testcase_45 | AC | 4 ms
4,380 KB |
testcase_46 | AC | 12 ms
4,380 KB |
testcase_47 | AC | 173 ms
5,624 KB |
testcase_48 | AC | 170 ms
5,620 KB |
testcase_49 | AC | 185 ms
5,620 KB |
testcase_50 | AC | 173 ms
5,540 KB |
testcase_51 | AC | 153 ms
5,268 KB |
testcase_52 | AC | 110 ms
4,952 KB |
testcase_53 | AC | 154 ms
5,208 KB |
testcase_54 | AC | 11 ms
4,376 KB |
testcase_55 | AC | 1 ms
4,376 KB |
testcase_56 | AC | 1 ms
4,380 KB |
testcase_57 | AC | 2 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Mo { const int width; vector<int> ls, rs, ord; Mo(int n) : width((int)sqrt(n)) {} inline void insert(int l, int r) { ls.emplace_back(l); rs.emplace_back(r); } inline void build() { ord.resize(ls.size()); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](const int a, const int b) { int ablock = ls[a] / width, bblock = ls[b] / width; if (ablock != bblock) return ablock < bblock; return ablock & 1 ? rs[a] < rs[b] : rs[a] > rs[b]; }); } // void add(int idx): idx番目の要素を追加 // void del(int idx): idx番目の要素を削除 // void calc(int idx); クエリidxを処理 template<class Add, class Del, class Calc> inline void run(const Add& add, const Del& del, const Calc& calc) { int nl = 0, nr = 0; for (const int idx : ord) { while (nl > ls[idx]) add(--nl); while (nr < rs[idx]) add(nr++); while (nl < ls[idx]) del(nl++); while (nr > rs[idx]) del(--nr); calc(idx); } } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<ll> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } Mo mo(n); vector< vector<int> > query_id(n + 1); int query_num = 0; for (int k = 1; k <= n; k++) { int max_num = n / k; for (int i = 0; i < max_num; i++) { query_id[k].push_back(query_num); mo.insert(i * k, (i + 1) * k); query_num++; } for (int i = 0; i < max_num; i++) { query_id[k].push_back(query_num); mo.insert(n - (i + 1) * k, n - i * k); query_num++; } } mo.build(); multiset<ll> sl, sr; auto add = [&](int idx) { if (sl.empty()) { sl.insert(a[idx]); return; } if (sr.empty()) { if (*sl.begin() <= a[idx]) sr.insert(a[idx]); else { ll tmp = *sl.begin(); sl.erase(sl.begin()); sl.insert(a[idx]); sr.insert(tmp); } return; } if (*sl.rbegin() <= a[idx] && a[idx] <= *sr.begin()) { if (sl.size() > sr.size()) sr.insert(a[idx]); else sl.insert(a[idx]); } else if (a[idx] > *sr.begin()) { if (sl.size() > sr.size()) sr.insert(a[idx]); else { ll tmp = *sr.begin(); sr.erase(sr.begin()); sl.insert(tmp); sr.insert(a[idx]); } } else { if (sl.size() == sr.size()) sl.insert(a[idx]); else { ll tmp = *sl.rbegin(); sl.erase(prev(sl.end())); sl.insert(a[idx]); sr.insert(tmp); } } }; auto del = [&](int idx) { assert(!sl.empty()); if (sr.empty()) { sl.erase(sl.find(a[idx])); return; } if (sl.size() > sr.size()) { if (a[idx] <= *sl.rbegin()) { sl.erase(sl.find(a[idx])); } else { ll tmp = *sl.rbegin(); sl.erase(prev(sl.end())); sr.erase(sr.find(a[idx])); sr.insert(tmp); } } else { if (a[idx] >= *sr.begin()) { sr.erase(sr.find(a[idx])); } else { ll tmp = *sr.begin(); sr.erase(sr.begin()); sl.erase(sl.find(a[idx])); sl.insert(tmp); } } }; vector<ll> med(query_num); auto calc = [&](int idx) { med[idx] = *sl.rbegin(); }; mo.run(add, del, calc); ll ans = 0; for (int k = 1; k <= n; k++) { int max_num = n / k; vector<ll> memoL(max_num + 1, 0); ll tmp = 0; for (int i = 0; i < max_num; i++) { tmp += med[query_id[k][i]] * k; memoL[i + 1] = max(memoL[i], tmp); } vector<ll> memoR(max_num + 1, 0); tmp = 0; for (int i = 0; i < max_num; i++) { tmp += med[query_id[k][i + max_num]] * k; memoR[i + 1] = max(memoR[i], tmp); } for (int i = 0; i <= max_num; i++) { ans = max(ans, memoL[i] + memoR[max_num - i]); } } cout << ans << "\n"; return 0; }