結果
問題 | No.919 You Are A Project Manager |
ユーザー |
![]() |
提出日時 | 2019-10-25 22:27:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 445 ms / 3,000 ms |
コード長 | 2,043 bytes |
コンパイル時間 | 1,119 ms |
コンパイル使用メモリ | 117,340 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2024-06-27 17:09:39 |
合計ジャッジ時間 | 11,698 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 55 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;int sz;vector<ll> seg[1<<15];int query(int a, int b, ll x){a+=sz, b+=sz;int ret=0;for(;a<b; a>>=1, b>>=1){if(b&1){b--;int k=upper_bound(seg[b].begin(), seg[b].end(), x)-seg[b].begin();ret+=k;}if(a&1){int k=upper_bound(seg[a].begin(), seg[a].end(), x)-seg[a].begin();a++;ret+=k;}}return ret;}ll a[10010];ll med(int p, int q){int len=q-p;if(len==1) return a[p];else if(len==2) return min(a[p], a[p+1]);ll l=-1e9-7, r=1e9+7;while(r-l>1){ll mid=(l+r)/2;if(query(p, q, mid)>=(len+1)/2) r=mid;else l=mid;}return r;}int main(){int n;cin>>n;for(int i=0; i<n; i++) cin>>a[i];sz=1;while(sz<n) sz<<=1;for(int i=0; i<n; i++) seg[i+sz].push_back(a[i]);for(int i=sz-1; i>=1; i--){for(auto x:seg[2*i]) seg[i].push_back(x);for(auto x:seg[2*i+1]) seg[i].push_back(x);sort(seg[i].begin(), seg[i].end());}ll ans=0;for(int k=1; k<=n; k++){vector<ll> sl(n/k+1), sr(n/k+1);for(int j=0; j<n/k; j++){sl[j+1]=sl[j]+med(j*k, (j+1)*k);}for(int j=0; j<n/k; j++){sr[j+1]=sr[j]+med(n-(j+1)*k, n-j*k);}ll mx=0;ans=max(ans, sr[n/k]*k);for(int j=1; j<=n/k; j++){mx=max(mx, sl[j]);ans=max(ans, (mx+sr[n/k-j])*k);}}cout<<ans<<endl;return 0;}