結果
問題 | No.919 You Are A Project Manager |
ユーザー |
|
提出日時 | 2019-09-25 09:41:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 845 ms / 3,000 ms |
コード長 | 3,705 bytes |
コンパイル時間 | 2,250 ms |
コンパイル使用メモリ | 196,176 KB |
実行使用メモリ | 16,872 KB |
最終ジャッジ日時 | 2024-06-27 16:54:58 |
合計ジャッジ時間 | 21,069 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 55 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <class T> inline void chmax(T& a, const T b){a=max(a,b);}inline void balanceLtoR(multiset<long long>& stl,multiset<long long>& str) {while(stl.size()>str.size()+1) {long long tmp = *stl.rbegin();str.insert(tmp);stl.erase(stl.find(tmp));}}inline void balanceRtoL(multiset<long long>& stl,multiset<long long>& str) {if(stl.size()<str.size()) {stl.insert(*str.begin());str.erase(str.begin());}}inline void exchange(multiset<long long>& stl,multiset<long long>& str){long long tmpl = *stl.rbegin();long long tmpr = *str.begin();if(tmpl>tmpr) {stl.erase(stl.find(tmpl));stl.insert(tmpr);str.erase(str.find(tmpr));str.insert(tmpl);}}int main() {cin.tie(0);ios::sync_with_stdio(false);int N; cin >> N;assert(1<=N && N <= 10000);vector<long long> A(N);for(int i = 0; i < N; ++i) cin >> A[i];for(int i = 0; i < N; ++i) assert(-1000000000<=A[i] && A[i] <= 1000000000);//クエリ区間を列挙、調和級数なのでO(N*logN)vector<pair<long long,long long>> range;for(int n = 1; n <= N; ++n) {int M = N/n;for(int i = 0; i+n <= N; i+=n) range.push_back({i,i+n-1});for(int i = N-M*n; i+n <= N; i+=n) range.push_back({i,i+n-1});}//Mo順ソート O(N*logN*log(NlogN))int bucket = max(1,(int)sqrt(N)-10);vector<int> idx(range.size());iota(idx.begin(),idx.end(),0);sort(idx.begin(),idx.end(),[&](int a, int b){auto al = range[a].first/bucket;auto& ar = range[a].second;auto bl = range[b].first/bucket;auto& br = range[b].second;return (al != bl) ? (al < bl) : ((al%2)?(ar > br):(ar < br));});//Moで中央値列挙 O(N*sqrt(N)*(logN)^2)int l = 0, r = 0;multiset<long long> stl,str;stl.insert(A[0]);unordered_map<long long,long long> mp;for(int& i:idx){auto& xl = range[i].first;auto& xr = range[i].second;//左端を広げるwhile(xl < l){l--;stl.insert(A[l]);if(str.size()) exchange(stl,str);balanceLtoR(stl,str);}//右端を広げるwhile(r < xr){r++;stl.insert(A[r]);if(str.size()) exchange(stl,str);balanceLtoR(stl,str);}//左端を狭めるwhile(l < xl){if(stl.find(A[l])!=stl.end()) {stl.erase(stl.find(A[l]));balanceRtoL(stl,str);}else {str.erase(str.find(A[l]));balanceLtoR(stl,str);}l++;}//右端を狭めるwhile(xr < r){if(stl.find(A[r])!=stl.end()) {stl.erase(stl.find(A[r]));balanceRtoL(stl,str);}else {str.erase(str.find(A[r]));balanceLtoR(stl,str);}r--;}mp[xl*N+xr] = *stl.rbegin();}long long ans = 0;int cnt = 0;//区間長決め打ち全探索O(N*logN)for(long long n = 1; n <= N; ++n) {int M = N/n;vector<long long> lSum(M,0),rSum(M,0);vector<pair<long long,long long>> lRange(M),rRange(M);//区間取得for(int i = 0; i < M; ++i) {lRange[i] = range[cnt + i];lSum[i] = n*mp[lRange[i].first*N+lRange[i].second];rRange[i] = range[cnt + i + M];rSum[i] = n*mp[rRange[i].first*N+rRange[i].second];}//累積和for(int i = 1; i < M; ++i) lSum[i] += lSum[i-1];for(int i = M-2; 0 <= i; --i) rSum[i] += rSum[i+1];//累積maxfor(int i = 1; i < M; ++i) chmax(lSum[i],lSum[i-1]);for(int i = M-2; 0 <= i; --i) chmax(rSum[i],rSum[i+1]);chmax(ans,lSum[M-1]);chmax(ans,rSum[0]);//尺取りしながら左右決め打ち全探索int j = 0;for(int i = 0; i < M; ++i) {while(j < M && lRange[i].second >= rRange[j].first) j++;if(j<M && lRange[i].second < rRange[j].first) {chmax(ans,lSum[i]+rSum[j]);}}cnt += 2*M;}cout << ans << endl;return 0;}