結果

問題 No.919 You Are A Project Manager
ユーザー ningenMe
提出日時 2019-10-25 20:21:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,950 bytes
コンパイル時間 2,526 ms
コンパイル使用メモリ 182,824 KB
実行使用メモリ 13,884 KB
最終ジャッジ日時 2024-07-21 20:41:27
合計ジャッジ時間 22,203 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 20 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template <class T> void chmax(T& a, const T b){a=max(a,b);}

template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}

int main() {
	cin.tie(0);ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<long long> A(N);
	for(int i = 0; i < N; ++i) cin >> A[i];
	long long ans = 0;
	
	for(long long k = 1; k <= N; ++k) {
		int M = N/k;
		int i = 0;
		vector<vector<long long>> vasc(M),vdsc(M);
		vector<pair<int,int>> rasc(M),rdsc(M);
		
		while(i+k<=N){
			int idx = i/k;
			for(int j = i;j<i+k;++j) {
				vasc[idx].push_back(A[j]);
			}
			sort(vasc[idx].begin(),vasc[idx].end());
			rasc[idx] = {i,i+k-1};
			i += k;
		}
		i = N-1;
		while(-1<=i-k){
			int idx = (N-1-i)/k;
			for(int j = i; i-k < j;--j) {
				vdsc[idx].push_back(A[j]);
			}
			sort(vdsc[idx].begin(),vdsc[idx].end());
			rdsc[idx] = {i-k+1,i};
			i -= k;
		}
		reverse(vdsc.begin(),vdsc.end());
		reverse(rdsc.begin(),rdsc.end());
		
		vector<long long> sasc(M,0),sdsc(M,0);
		for(int i = 0;    i < M; ++i) sasc[i]  = k*vasc[i][(k-1)/2];
		for(int i = M-1; 0 <= i; --i) sdsc[i]  = k*vdsc[i][(k-1)/2];
		for(int i = 1;    i < M; ++i) sasc[i] += sasc[i-1];
		for(int i = M-2; 0 <= i; --i) sdsc[i] += sdsc[i+1];
		for(int i = 1;    i < M; ++i) chmax(sasc[i],sasc[i-1]);
		for(int i = M-2; 0 <= i; --i) chmax(sdsc[i],sdsc[i+1]);
		chmax(ans,sasc.back());
		chmax(ans,sdsc.front());
		int j = 0;
		for(int i = 0; i < M; ++i) {
			while(j < M && rasc[i].second >= rdsc[j].first) j++;
			if(j<M && rasc[i].second < rdsc[j].first) {
				chmax(ans,sasc[i]+sdsc[j]);
			}
		}
 	}
	cout << ans << endl;
    return 0;
}
0