結果
問題 | No.919 You Are A Project Manager |
ユーザー | mamekin |
提出日時 | 2019-11-06 20:00:54 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,322 ms / 3,000 ms |
コード長 | 2,511 bytes |
コンパイル時間 | 1,126 ms |
コンパイル使用メモリ | 120,616 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-10 03:55:08 |
合計ジャッジ時間 | 35,161 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,385 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 21 ms
4,380 KB |
testcase_05 | AC | 24 ms
4,376 KB |
testcase_06 | AC | 3 ms
4,376 KB |
testcase_07 | AC | 434 ms
4,380 KB |
testcase_08 | AC | 37 ms
4,380 KB |
testcase_09 | AC | 21 ms
4,376 KB |
testcase_10 | AC | 57 ms
4,376 KB |
testcase_11 | AC | 52 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 83 ms
4,376 KB |
testcase_14 | AC | 3 ms
4,376 KB |
testcase_15 | AC | 12 ms
4,380 KB |
testcase_16 | AC | 149 ms
4,376 KB |
testcase_17 | AC | 347 ms
4,380 KB |
testcase_18 | AC | 344 ms
4,380 KB |
testcase_19 | AC | 1,411 ms
4,376 KB |
testcase_20 | AC | 1,961 ms
4,380 KB |
testcase_21 | AC | 1,387 ms
4,380 KB |
testcase_22 | AC | 498 ms
4,380 KB |
testcase_23 | AC | 477 ms
4,380 KB |
testcase_24 | AC | 532 ms
4,380 KB |
testcase_25 | AC | 500 ms
4,380 KB |
testcase_26 | AC | 1,882 ms
4,384 KB |
testcase_27 | AC | 1,505 ms
4,376 KB |
testcase_28 | AC | 2,215 ms
4,376 KB |
testcase_29 | AC | 343 ms
4,380 KB |
testcase_30 | AC | 344 ms
4,376 KB |
testcase_31 | AC | 325 ms
4,376 KB |
testcase_32 | AC | 341 ms
4,380 KB |
testcase_33 | AC | 586 ms
4,380 KB |
testcase_34 | AC | 586 ms
4,376 KB |
testcase_35 | AC | 2,309 ms
4,384 KB |
testcase_36 | AC | 2,305 ms
4,380 KB |
testcase_37 | AC | 2,311 ms
4,380 KB |
testcase_38 | AC | 2,322 ms
4,384 KB |
testcase_39 | AC | 2 ms
4,376 KB |
testcase_40 | AC | 13 ms
4,380 KB |
testcase_41 | AC | 2 ms
4,376 KB |
testcase_42 | AC | 3 ms
4,376 KB |
testcase_43 | AC | 5 ms
4,380 KB |
testcase_44 | AC | 20 ms
4,380 KB |
testcase_45 | AC | 3 ms
4,376 KB |
testcase_46 | AC | 15 ms
4,380 KB |
testcase_47 | AC | 503 ms
4,376 KB |
testcase_48 | AC | 488 ms
4,380 KB |
testcase_49 | AC | 550 ms
4,376 KB |
testcase_50 | AC | 495 ms
4,376 KB |
testcase_51 | AC | 424 ms
4,376 KB |
testcase_52 | AC | 277 ms
4,380 KB |
testcase_53 | AC | 424 ms
4,384 KB |
testcase_54 | AC | 12 ms
4,376 KB |
testcase_55 | AC | 1 ms
4,384 KB |
testcase_56 | AC | 2 ms
4,384 KB |
testcase_57 | AC | 2 ms
4,380 KB |
ソースコード
#define _USE_MATH_DEFINES #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <vector> #include <array> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <iterator> #include <memory> #include <regex> using namespace std; class Xorshift { private: uint32_t x, y, z, w; public: Xorshift(uint32_t seed=88675123, int32_t loop=50){ x = 123456789; y = 362436069; z = 521288629; w = seed; while(--loop >= 0){ (*this)(); } } uint32_t operator()(){ uint32_t t=(x^(x<<11)); x=y; y=z; z=w; return w=(w^(w>>19))^(t^(t>>8)); } uint32_t operator()(uint32_t size){ return (*this)() % size; } }; Xorshift xorshift; int quickSelect(vector<int>::iterator left, vector<int>::iterator right, int index) { int n = right - left; if(n == 1) return *left; swap(*left, *(left + xorshift(n))); auto it1 = left + 1; auto it2 = right - 1; int m1 = 0; int m2 = 0; while(it1 <= it2){ if(*it1 < *left || (*it1 == *left && m1 < m2)){ ++ it1; ++ m1; } else{ swap(*it1, *it2); -- it2; ++ m2; } } swap(*left, *it2); if(index < m1) return quickSelect(left, it2, index); else if(index == m1) return *it2; else return quickSelect(it1, right, index - m1 - 1); } int main() { int n; cin >> n; vector<int> a(n); for(int i=0; i<n; ++i) cin >> a[i]; long long ans = 0; for(int len=1; len<=n; ++len){ int m = n / len; vector<int> a1 = a; vector<int> a2 = a; vector<long long> v1(m+1), v2(m+1); for(int i=0; i<m; ++i){ v1[i+1] = v1[i] + quickSelect(a1.begin() + len * i, a1.begin() + len * (i + 1), (len - 1) / 2); v2[i+1] = v2[i] + quickSelect(a2.end() - len * (i + 1), a2.end() - len * i, (len - 1) / 2); } for(int i=0; i<m; ++i){ v1[i+1] = max(v1[i+1], v1[i]); v2[i+1] = max(v2[i+1], v2[i]); } for(int i=0; i<=m; ++i) ans = max(ans, (v1[i] + v2[m-i]) * len); } cout << ans << endl; return 0; }