#392718 (C++14) No.919 You Are A Project Manager

提出ソース

結果

問題	No.919 You Are A Project Manager
ユーザー	ningenMe
提出日時	2019-10-25 08:30:31
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	2,968 bytes
コンパイル時間	1,760 ms
コンパイル使用メモリ	181,012 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-19 04:01:56
合計ジャッジ時間	29,730 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	99 ms 5,376 KB
testcase_05	AC	113 ms 5,376 KB
testcase_06	AC	6 ms 5,376 KB
testcase_07	AC	1,385 ms 5,376 KB
testcase_08	AC	98 ms 5,376 KB
testcase_09	AC	55 ms 5,376 KB
testcase_10	AC	157 ms 5,376 KB
testcase_11	AC	140 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	248 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	25 ms 5,376 KB
testcase_16	AC	468 ms 5,376 KB
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	AC	1,647 ms 5,376 KB
testcase_23	AC	1,599 ms 5,376 KB
testcase_24	AC	1,766 ms 5,376 KB
testcase_25	AC	1,694 ms 5,376 KB
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-
testcase_33	AC	1,984 ms 5,376 KB
testcase_34	AC	1,940 ms 5,376 KB
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-
testcase_38	RE	-
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	28 ms 5,376 KB
testcase_41	AC	4 ms 5,376 KB
testcase_42	AC	5 ms 5,376 KB
testcase_43	AC	11 ms 5,376 KB
testcase_44	AC	50 ms 5,376 KB
testcase_45	AC	5 ms 5,376 KB
testcase_46	AC	35 ms 5,376 KB
testcase_47	AC	1,676 ms 5,376 KB
testcase_48	AC	1,638 ms 5,376 KB
testcase_49	AC	1,850 ms 5,376 KB
testcase_50	AC	1,643 ms 5,376 KB
testcase_51	AC	1,388 ms 5,376 KB
testcase_52	AC	874 ms 5,376 KB
testcase_53	AC	1,382 ms 5,376 KB
testcase_54	AC	29 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	2 ms 5,376 KB
testcase_57	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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];
	assert(N<=5000);
	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;
}

yukicoder

結果

テストケース

ソースコード