結果

問題 No.919 You Are A Project Manager
ユーザー ningenMe
提出日時 2019-10-25 08:34:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,229 bytes
コンパイル時間 1,965 ms
コンパイル使用メモリ 183,744 KB
実行使用メモリ 14,016 KB
最終ジャッジ日時 2024-07-19 04:07:50
合計ジャッジ時間 27,061 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 17 WA * 2 TLE * 2 -- * 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;

	random_device rnd;     // 非決定的な乱数生成器を生成
    mt19937 mt(rnd());     //  メルセンヌ・ツイスタの32ビット版、引数は初期シード値
    uniform_int_distribution<> randK(1, N);        // [0, 99] 範囲の一様乱数

	for(int t = 0; t <= 10000; ++t) {
		int k = randK(mt);
		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