結果
問題 | No.919 You Are A Project Manager |
ユーザー | fine |
提出日時 | 2019-11-08 23:25:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 733 ms / 3,000 ms |
コード長 | 3,706 bytes |
コンパイル時間 | 5,147 ms |
コンパイル使用メモリ | 180,580 KB |
実行使用メモリ | 8,908 KB |
最終ジャッジ日時 | 2023-09-10 03:56:58 |
合計ジャッジ時間 | 19,360 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 724 ms
8,908 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 72 ms
4,380 KB |
testcase_05 | AC | 82 ms
4,380 KB |
testcase_06 | AC | 4 ms
4,380 KB |
testcase_07 | AC | 175 ms
5,224 KB |
testcase_08 | AC | 27 ms
4,384 KB |
testcase_09 | AC | 18 ms
4,380 KB |
testcase_10 | AC | 37 ms
4,380 KB |
testcase_11 | AC | 34 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 47 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 11 ms
4,380 KB |
testcase_16 | AC | 77 ms
4,380 KB |
testcase_17 | AC | 635 ms
8,696 KB |
testcase_18 | AC | 632 ms
8,728 KB |
testcase_19 | AC | 733 ms
8,832 KB |
testcase_20 | AC | 584 ms
7,980 KB |
testcase_21 | AC | 724 ms
8,904 KB |
testcase_22 | AC | 194 ms
5,636 KB |
testcase_23 | AC | 189 ms
5,420 KB |
testcase_24 | AC | 206 ms
5,428 KB |
testcase_25 | AC | 193 ms
5,628 KB |
testcase_26 | AC | 556 ms
8,108 KB |
testcase_27 | AC | 465 ms
7,604 KB |
testcase_28 | AC | 642 ms
8,828 KB |
testcase_29 | AC | 652 ms
8,532 KB |
testcase_30 | AC | 634 ms
8,532 KB |
testcase_31 | AC | 633 ms
8,644 KB |
testcase_32 | AC | 635 ms
8,596 KB |
testcase_33 | AC | 218 ms
5,796 KB |
testcase_34 | AC | 219 ms
5,744 KB |
testcase_35 | AC | 661 ms
8,640 KB |
testcase_36 | AC | 665 ms
8,724 KB |
testcase_37 | AC | 664 ms
8,644 KB |
testcase_38 | AC | 667 ms
8,596 KB |
testcase_39 | AC | 2 ms
4,384 KB |
testcase_40 | AC | 11 ms
4,384 KB |
testcase_41 | AC | 3 ms
4,380 KB |
testcase_42 | AC | 4 ms
4,380 KB |
testcase_43 | AC | 6 ms
4,384 KB |
testcase_44 | AC | 16 ms
4,376 KB |
testcase_45 | AC | 4 ms
4,380 KB |
testcase_46 | AC | 14 ms
4,376 KB |
testcase_47 | AC | 196 ms
5,640 KB |
testcase_48 | AC | 191 ms
5,412 KB |
testcase_49 | AC | 208 ms
5,488 KB |
testcase_50 | AC | 197 ms
5,584 KB |
testcase_51 | AC | 175 ms
5,152 KB |
testcase_52 | AC | 122 ms
4,868 KB |
testcase_53 | AC | 172 ms
5,328 KB |
testcase_54 | AC | 11 ms
4,384 KB |
testcase_55 | AC | 2 ms
4,376 KB |
testcase_56 | AC | 2 ms
4,380 KB |
testcase_57 | AC | 1 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 (sr.size() > sl.size()) { sr.insert(a[idx]); } else { sl.insert(a[idx]); } if (sl.size() > sr.size()) { ll tmp = *sl.rbegin(); sl.erase(sl.find(tmp)); sr.insert(tmp); } else if (sr.size() > sl.size() + 1) { ll tmp = *sr.begin(); sr.erase(sr.begin()); sl.insert(tmp); } }; auto del = [&](int idx) { assert(!sr.empty()); if (a[idx] >= *sr.begin()) { sr.erase(sr.find(a[idx])); } else { sl.erase(sl.find(a[idx])); } if (sl.size() > sr.size()) { ll tmp = *sl.rbegin(); sl.erase(sl.find(tmp)); sr.insert(tmp); } else if (sr.size() > sl.size() + 1) { ll tmp = *sr.begin(); sr.erase(sr.begin()); sl.insert(tmp); } }; vector<ll> med(query_num); auto calc = [&](int idx) { med[idx] = (sr.size() == sl.size() ? *sl.rbegin() : *sr.begin()); }; 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; }