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

提出ソース

結果

問題	No.919 You Are A Project Manager
ユーザー	ningenMe
提出日時	2019-10-25 20:02:08
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	3,364 bytes
コンパイル時間	2,067 ms
コンパイル使用メモリ	184,416 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-07-21 20:14:49
合計ジャッジ時間	119,346 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,923 ms 6,816 KB
testcase_01	AC	2,915 ms 6,816 KB
testcase_02	AC	2,916 ms 6,944 KB
testcase_03	AC	2,914 ms 6,940 KB
testcase_04	AC	2,914 ms 6,940 KB
testcase_05	AC	2,916 ms 6,944 KB
testcase_06	AC	2,919 ms 6,940 KB
testcase_07	AC	2,918 ms 6,940 KB
testcase_08	AC	2,921 ms 6,940 KB
testcase_09	AC	2,915 ms 6,940 KB
testcase_10	AC	2,917 ms 6,944 KB
testcase_11	AC	2,916 ms 6,944 KB
testcase_12	AC	2,921 ms 6,940 KB
testcase_13	AC	2,915 ms 6,940 KB
testcase_14	AC	2,916 ms 6,940 KB
testcase_15	AC	2,916 ms 6,944 KB
testcase_16	AC	2,916 ms 6,940 KB
testcase_17	AC	2,918 ms 6,944 KB
testcase_18	AC	2,928 ms 6,940 KB
testcase_19	WA	-
testcase_20	AC	2,920 ms 6,944 KB
testcase_21	AC	2,917 ms 6,944 KB
testcase_22	AC	2,917 ms 6,940 KB
testcase_23	WA	-
testcase_24	AC	2,917 ms 6,944 KB
testcase_25	AC	2,917 ms 6,944 KB
testcase_26	AC	2,918 ms 6,944 KB
testcase_27	AC	2,919 ms 6,940 KB
testcase_28	WA	-
testcase_29	AC	2,917 ms 6,940 KB
testcase_30	AC	2,918 ms 6,944 KB
testcase_31	AC	2,918 ms 6,940 KB
testcase_32	AC	2,925 ms 6,944 KB
testcase_33	WA	-
testcase_34	AC	2,916 ms 6,944 KB
testcase_35	WA	-
testcase_36	WA	-
testcase_37	AC	2,917 ms 6,944 KB
testcase_38	AC	2,922 ms 6,948 KB
testcase_39	AC	2,921 ms 6,940 KB
testcase_40	AC	2,916 ms 6,944 KB
testcase_41	AC	2,915 ms 6,940 KB
testcase_42	AC	2,915 ms 6,940 KB
testcase_43	AC	2,915 ms 6,944 KB
testcase_44	AC	2,916 ms 6,948 KB
testcase_45	AC	2,915 ms 6,948 KB
testcase_46	AC	2,916 ms 6,944 KB
testcase_47	AC	2,918 ms 6,944 KB
testcase_48	AC	2,918 ms 6,944 KB
testcase_49	WA	-
testcase_50	AC	2,914 ms 6,940 KB
testcase_51	WA	-
testcase_52	AC	2,915 ms 6,940 KB
testcase_53	AC	2,916 ms 6,944 KB
testcase_54	AC	2,917 ms 6,940 KB
testcase_55	AC	2,913 ms 6,944 KB
testcase_56	AC	2,913 ms 6,940 KB
testcase_57	AC	2,913 ms 6,944 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);

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

yukicoder

結果

テストケース

ソースコード