結果
問題 | No.919 You Are A Project Manager |
ユーザー | leaf_1415 |
提出日時 | 2019-10-26 01:57:23 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 642 ms / 3,000 ms |
コード長 | 2,428 bytes |
コンパイル時間 | 1,769 ms |
コンパイル使用メモリ | 91,780 KB |
実行使用メモリ | 19,092 KB |
最終ジャッジ日時 | 2023-09-10 01:40:05 |
合計ジャッジ時間 | 16,487 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 505 ms
17,940 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 54 ms
6,016 KB |
testcase_05 | AC | 60 ms
6,268 KB |
testcase_06 | AC | 4 ms
4,376 KB |
testcase_07 | AC | 175 ms
9,512 KB |
testcase_08 | AC | 27 ms
4,376 KB |
testcase_09 | AC | 18 ms
4,376 KB |
testcase_10 | AC | 37 ms
4,552 KB |
testcase_11 | AC | 35 ms
4,576 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 47 ms
4,828 KB |
testcase_14 | AC | 3 ms
4,376 KB |
testcase_15 | AC | 12 ms
4,376 KB |
testcase_16 | AC | 77 ms
6,068 KB |
testcase_17 | AC | 408 ms
16,316 KB |
testcase_18 | AC | 402 ms
16,432 KB |
testcase_19 | AC | 506 ms
16,272 KB |
testcase_20 | AC | 580 ms
16,648 KB |
testcase_21 | AC | 506 ms
17,216 KB |
testcase_22 | AC | 197 ms
8,992 KB |
testcase_23 | AC | 190 ms
9,080 KB |
testcase_24 | AC | 208 ms
9,332 KB |
testcase_25 | AC | 192 ms
8,944 KB |
testcase_26 | AC | 541 ms
16,788 KB |
testcase_27 | AC | 458 ms
15,044 KB |
testcase_28 | AC | 611 ms
18,008 KB |
testcase_29 | AC | 415 ms
17,580 KB |
testcase_30 | AC | 409 ms
17,012 KB |
testcase_31 | AC | 410 ms
17,924 KB |
testcase_32 | AC | 409 ms
18,112 KB |
testcase_33 | AC | 215 ms
10,088 KB |
testcase_34 | AC | 216 ms
9,516 KB |
testcase_35 | AC | 638 ms
19,092 KB |
testcase_36 | AC | 639 ms
16,592 KB |
testcase_37 | AC | 641 ms
16,608 KB |
testcase_38 | AC | 642 ms
17,728 KB |
testcase_39 | AC | 2 ms
4,380 KB |
testcase_40 | AC | 12 ms
4,380 KB |
testcase_41 | AC | 3 ms
4,380 KB |
testcase_42 | AC | 5 ms
4,376 KB |
testcase_43 | AC | 6 ms
4,380 KB |
testcase_44 | AC | 17 ms
4,376 KB |
testcase_45 | AC | 4 ms
4,376 KB |
testcase_46 | AC | 13 ms
4,380 KB |
testcase_47 | AC | 194 ms
9,104 KB |
testcase_48 | AC | 194 ms
8,848 KB |
testcase_49 | AC | 207 ms
9,120 KB |
testcase_50 | AC | 198 ms
9,748 KB |
testcase_51 | AC | 174 ms
8,684 KB |
testcase_52 | AC | 122 ms
6,808 KB |
testcase_53 | AC | 171 ms
8,888 KB |
testcase_54 | AC | 12 ms
4,376 KB |
testcase_55 | AC | 2 ms
4,376 KB |
testcase_56 | AC | 1 ms
4,376 KB |
testcase_57 | AC | 1 ms
4,384 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; }