結果
問題 | No.919 You Are A Project Manager |
ユーザー | leaf_1415 |
提出日時 | 2019-10-26 01:57:23 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 585 ms / 3,000 ms |
コード長 | 2,428 bytes |
コンパイル時間 | 1,356 ms |
コンパイル使用メモリ | 90,716 KB |
実行使用メモリ | 16,440 KB |
最終ジャッジ日時 | 2024-06-27 17:46:30 |
合計ジャッジ時間 | 14,882 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 542 ms
16,312 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 58 ms
6,140 KB |
testcase_05 | AC | 65 ms
6,272 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | AC | 164 ms
8,716 KB |
testcase_08 | AC | 26 ms
5,376 KB |
testcase_09 | AC | 17 ms
5,376 KB |
testcase_10 | AC | 34 ms
5,376 KB |
testcase_11 | AC | 33 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 44 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 11 ms
5,376 KB |
testcase_16 | AC | 72 ms
6,272 KB |
testcase_17 | AC | 456 ms
16,304 KB |
testcase_18 | AC | 455 ms
16,436 KB |
testcase_19 | AC | 537 ms
16,308 KB |
testcase_20 | AC | 522 ms
15,412 KB |
testcase_21 | AC | 546 ms
16,308 KB |
testcase_22 | AC | 180 ms
9,108 KB |
testcase_23 | AC | 174 ms
8,980 KB |
testcase_24 | AC | 188 ms
9,232 KB |
testcase_25 | AC | 176 ms
8,976 KB |
testcase_26 | AC | 502 ms
15,280 KB |
testcase_27 | AC | 425 ms
14,376 KB |
testcase_28 | AC | 565 ms
16,056 KB |
testcase_29 | AC | 458 ms
16,432 KB |
testcase_30 | AC | 452 ms
16,440 KB |
testcase_31 | AC | 456 ms
16,308 KB |
testcase_32 | AC | 462 ms
16,312 KB |
testcase_33 | AC | 201 ms
9,356 KB |
testcase_34 | AC | 199 ms
9,360 KB |
testcase_35 | AC | 585 ms
16,440 KB |
testcase_36 | AC | 578 ms
16,308 KB |
testcase_37 | AC | 585 ms
16,308 KB |
testcase_38 | AC | 580 ms
16,308 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 11 ms
5,376 KB |
testcase_41 | AC | 3 ms
5,376 KB |
testcase_42 | AC | 4 ms
5,376 KB |
testcase_43 | AC | 7 ms
5,376 KB |
testcase_44 | AC | 16 ms
5,376 KB |
testcase_45 | AC | 4 ms
5,376 KB |
testcase_46 | AC | 13 ms
5,376 KB |
testcase_47 | AC | 180 ms
9,032 KB |
testcase_48 | AC | 177 ms
9,100 KB |
testcase_49 | AC | 193 ms
9,232 KB |
testcase_50 | AC | 182 ms
8,988 KB |
testcase_51 | AC | 161 ms
8,716 KB |
testcase_52 | AC | 113 ms
6,916 KB |
testcase_53 | AC | 157 ms
8,840 KB |
testcase_54 | AC | 11 ms
5,376 KB |
testcase_55 | AC | 2 ms
5,376 KB |
testcase_56 | AC | 2 ms
5,376 KB |
testcase_57 | AC | 1 ms
5,376 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <cmath> #include <set> #define llint long long using namespace std; typedef pair<llint, llint> P; typedef pair<P, P> Q; llint n, B; llint a[10005]; vector<Q> qvec; vector<P> avec; multiset<llint> head, tail; vector<llint> lvec, rvec; void adjust(llint m) { while((int)head.size() > (m+1)/2){ auto it = head.end(); it--; tail.insert(*it), head.erase(it); } while((int)head.size() < (m+1)/2){ head.insert(*tail.begin()), tail.erase(tail.begin()); } } void add(llint x) { llint m = head.size() + tail.size(); if(head.size() == 0) head.insert(x); else{ auto it = head.end(); it--; if(*it >= x) head.insert(x); else tail.insert(x); } m++; adjust(m); } void erase(llint x) { llint m = head.size() + tail.size(); if(head.count(x)) head.erase(head.lower_bound(x)); else tail.erase(tail.lower_bound(x)); m--; adjust(m); } llint get() { auto it = head.end(); it--; return *it; } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; B = sqrt(n); llint qid = 0; for(int k = 1; k <= n; k++){ llint l, r; for(int i = 1; k*i <= n; i++){ l = (i-1)*k+1, r = i*k; qvec.push_back(Q(P(l/B, r), P(l, qid++))); l = n-i*k+1, r = n-(i-1)*k; qvec.push_back(Q(P(l/B, r), P(l, qid++))); } } sort(qvec.begin(), qvec.end()); llint l = qvec[0].second.first, r = qvec[0].first.second; for(int i = l; i <= r; i++) add(a[i]); avec.push_back(make_pair(qvec[0].second.second, get())); for(int i = 1; i < qvec.size(); i++){ llint nl = qvec[i].second.first, nr = qvec[i].first.second; while(l < nl) erase(a[l]), l++; while(l > nl) l--, add(a[l]); while(r < nr) r++, add(a[r]); while(r > nr) erase(a[r]), r--; llint qid = qvec[i].second.second; avec.push_back(make_pair(qid, get())); } sort(avec.begin(), avec.end()); llint ans = 0; qid = 0; for(int k = 1; k <= n; k++){ lvec.clear(), rvec.clear(); lvec.push_back(0), rvec.push_back(0); for(int i = 1; k*i <= n; i++){ lvec.push_back(avec[qid++].second); rvec.push_back(avec[qid++].second); } int m = (int)lvec.size() - 1; for(int i = 1; i <= m; i++) lvec[i] += lvec[i-1], rvec[i] += rvec[i-1]; llint mx = 0; for(int i = 0; i <= m; i++){ mx = max(mx, lvec[i]); ans = max(ans, k*(mx + rvec[m-i])); } } cout << ans << endl; return 0; }