結果

問題 No.919 You Are A Project Manager
ユーザー ningenMe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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];
//max
for(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0