結果

問題 No.919 You Are A Project Manager
ユーザー ningenMeningenMe
提出日時 2019-10-25 20:02:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,364 bytes
コンパイル時間 1,906 ms
コンパイル使用メモリ 181,092 KB
実行使用メモリ 7,928 KB
最終ジャッジ日時 2023-09-29 01:35:44
合計ジャッジ時間 41,985 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,918 ms
7,928 KB
testcase_01 AC 2,915 ms
4,376 KB
testcase_02 AC 2,915 ms
4,376 KB
testcase_03 AC 2,915 ms
4,376 KB
testcase_04 AC 2,916 ms
4,376 KB
testcase_05 AC 2,915 ms
4,380 KB
testcase_06 AC 2,915 ms
4,380 KB
testcase_07 AC 2,915 ms
4,440 KB
testcase_08 AC 2,919 ms
4,376 KB
testcase_09 AC 2,916 ms
4,380 KB
testcase_10 AC 2,916 ms
4,500 KB
testcase_11 AC 2,920 ms
4,376 KB
testcase_12 AC 2,914 ms
4,380 KB
testcase_13 AC 2,917 ms
4,380 KB
testcase_14 AC 2,916 ms
4,376 KB
testcase_15 AC 2,916 ms
4,376 KB
testcase_16 AC 2,916 ms
4,380 KB
testcase_17 AC 2,917 ms
5,048 KB
testcase_18 AC 2,921 ms
4,884 KB
testcase_19 AC 2,918 ms
5,084 KB
testcase_20 WA -
testcase_21 AC 2,917 ms
4,744 KB
testcase_22 AC 2,917 ms
4,400 KB
testcase_23 TLE -
testcase_24 AC 2,916 ms
4,376 KB
testcase_25 AC 2,918 ms
4,380 KB
testcase_26 AC 2,920 ms
4,380 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 2,916 ms
4,788 KB
testcase_30 AC 2,917 ms
5,016 KB
testcase_31 AC 2,989 ms
4,648 KB
testcase_32 WA -
testcase_33 AC 2,917 ms
4,380 KB
testcase_34 AC 2,916 ms
4,380 KB
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 2,921 ms
4,376 KB
testcase_40 TLE -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
権限があれば一括ダウンロードができます

ソースコード

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);

    clock_t start = clock();


	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] 範囲の一様乱数


	while(1) {
		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]);
			}
		}
		clock_t end = clock();
		double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
		if(time>2900.) break;
 	}
	cout << ans << endl;
    return 0;
}
0