結果
問題 | No.919 You Are A Project Manager |
ユーザー | miyo2580 |
提出日時 | 2024-02-05 22:42:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 83 ms / 3,000 ms |
コード長 | 5,372 bytes |
コンパイル時間 | 3,678 ms |
コンパイル使用メモリ | 315,952 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-28 11:47:54 |
合計ジャッジ時間 | 6,919 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 54 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 11 ms
5,376 KB |
testcase_05 | AC | 13 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 30 ms
5,376 KB |
testcase_08 | AC | 8 ms
5,376 KB |
testcase_09 | AC | 6 ms
5,376 KB |
testcase_10 | AC | 11 ms
5,376 KB |
testcase_11 | AC | 11 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 12 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 5 ms
5,376 KB |
testcase_16 | AC | 18 ms
5,376 KB |
testcase_17 | AC | 50 ms
5,376 KB |
testcase_18 | AC | 47 ms
5,376 KB |
testcase_19 | AC | 52 ms
5,376 KB |
testcase_20 | AC | 76 ms
5,376 KB |
testcase_21 | AC | 52 ms
5,376 KB |
testcase_22 | AC | 33 ms
5,376 KB |
testcase_23 | AC | 33 ms
5,376 KB |
testcase_24 | AC | 35 ms
5,376 KB |
testcase_25 | AC | 34 ms
5,376 KB |
testcase_26 | AC | 73 ms
5,376 KB |
testcase_27 | AC | 64 ms
5,376 KB |
testcase_28 | AC | 83 ms
5,376 KB |
testcase_29 | AC | 47 ms
5,376 KB |
testcase_30 | AC | 49 ms
5,376 KB |
testcase_31 | AC | 48 ms
5,376 KB |
testcase_32 | AC | 48 ms
5,376 KB |
testcase_33 | AC | 37 ms
5,376 KB |
testcase_34 | AC | 37 ms
5,376 KB |
testcase_35 | AC | 82 ms
5,376 KB |
testcase_36 | AC | 83 ms
5,376 KB |
testcase_37 | AC | 82 ms
5,376 KB |
testcase_38 | AC | 82 ms
5,376 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 5 ms
5,376 KB |
testcase_41 | AC | 3 ms
5,376 KB |
testcase_42 | AC | 3 ms
5,376 KB |
testcase_43 | AC | 4 ms
5,376 KB |
testcase_44 | AC | 7 ms
5,376 KB |
testcase_45 | AC | 3 ms
5,376 KB |
testcase_46 | AC | 5 ms
5,376 KB |
testcase_47 | AC | 35 ms
5,376 KB |
testcase_48 | AC | 33 ms
5,376 KB |
testcase_49 | AC | 35 ms
5,376 KB |
testcase_50 | AC | 34 ms
5,376 KB |
testcase_51 | AC | 31 ms
5,376 KB |
testcase_52 | AC | 25 ms
5,376 KB |
testcase_53 | AC | 32 ms
5,376 KB |
testcase_54 | AC | 6 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 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define repd(i,a,b) for (ll i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } typedef long long ll; typedef pair<ll,ll> P; typedef vector<ll> vec; using Graph = vector<vector<ll>>; const long long INF = 1LL<<60; const long long MOD = 1000000007; //https://nyaannyaan.github.io/library/data-structure-2d/wavelet-matrix.hpp.html #include <immintrin.h> struct bit_vector { using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; static constexpr u32 w = 64; vector<u64> block; vector<u32> count; u32 n, zeros; inline u32 get(u32 i) const { return u32(block[i / w] >> (i % w)) & 1u; } inline void set(u32 i) { block[i / w] |= 1LL << (i % w); } bit_vector() {} bit_vector(int _n) { init(_n); } __attribute__((optimize("O3", "unroll-loops"))) void init(int _n) { n = zeros = _n; block.resize(n / w + 1, 0); count.resize(block.size(), 0); } __attribute__((target("popcnt"))) void build() { for (u32 i = 1; i < block.size(); ++i) count[i] = count[i - 1] + _mm_popcnt_u64(block[i - 1]); zeros = rank0(n); } inline u32 rank0(u32 i) const { return i - rank1(i); } __attribute__((target("bmi2,popcnt"))) inline u32 rank1(u32 i) const { return count[i / w] + _mm_popcnt_u64(_bzhi_u64(block[i / w], i % w)); } }; template <typename T> struct WaveletMatrix { using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; int n, lg; vector<T> a; vector<bit_vector> bv; WaveletMatrix(u32 _n) : n(max<u32>(_n, 1)), a(n) {} WaveletMatrix(const vector<T>& _a) : n(_a.size()), a(_a) { build(); } __attribute__((optimize("O3"))) void build() { lg = __lg(max<T>(*max_element(begin(a), end(a)), 1)) + 1; bv.assign(lg, n); vector<T> cur = a, nxt(n); for (int h = lg - 1; h >= 0; --h) { for (int i = 0; i < n; ++i) if ((cur[i] >> h) & 1) bv[h].set(i); bv[h].build(); array<decltype(begin(nxt)), 2> it{begin(nxt), begin(nxt) + bv[h].zeros}; for (int i = 0; i < n; ++i) *it[bv[h].get(i)]++ = cur[i]; swap(cur, nxt); } return; } void set(u32 i, const T& x) { assert(x >= 0); a[i] = x; } inline pair<u32, u32> succ0(int l, int r, int h) const { return make_pair(bv[h].rank0(l), bv[h].rank0(r)); } inline pair<u32, u32> succ1(int l, int r, int h) const { u32 l0 = bv[h].rank0(l); u32 r0 = bv[h].rank0(r); u32 zeros = bv[h].zeros; return make_pair(l + zeros - l0, r + zeros - r0); } // return a[k] T access(u32 k) const { T ret = 0; for (int h = lg - 1; h >= 0; --h) { u32 f = bv[h].get(k); ret |= f ? T(1) << h : 0; k = f ? bv[h].rank1(k) + bv[h].zeros : bv[h].rank0(k); } return ret; } // k-th (0-indexed) smallest number in a[l, r) T kth_smallest(u32 l, u32 r, u32 k) const { T res = 0; for (int h = lg - 1; h >= 0; --h) { u32 l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if (k < r0 - l0) l = l0, r = r0; else { k -= r0 - l0; res |= (T)1 << h; l += bv[h].zeros - l0; r += bv[h].zeros - r0; } } return res; } // k-th (0-indexed) largest number in a[l, r) T kth_largest(int l, int r, int k) { return kth_smallest(l, r, r - l - k - 1); } // count i s.t. (l <= i < r) && (v[i] < upper) int range_freq(int l, int r, T upper) { if (upper >= (T(1) << lg)) return r - l; int ret = 0; for (int h = lg - 1; h >= 0; --h) { bool f = (upper >> h) & 1; u32 l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if (f) { ret += r0 - l0; l += bv[h].zeros - l0; r += bv[h].zeros - r0; } else { l = l0; r = r0; } } return ret; } int range_freq(int l, int r, T lower, T upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); } // max v[i] s.t. (l <= i < r) && (v[i] < upper) T prev_value(int l, int r, T upper) { int cnt = range_freq(l, r, upper); return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1); } // min v[i] s.t. (l <= i < r) && (lower <= v[i]) T next_value(int l, int r, T lower) { int cnt = range_freq(l, r, lower); return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt); } }; /* * @brief Wavelet Matrix * @docs docs/data-structure-2d/wavelet-matrix.md */ ll mx=1000000000; int main() { ios::sync_with_stdio(false); cin.tie(0); ll n;cin>>n; vec a(n); rep(i,n)cin>>a[i]; WaveletMatrix<ll> w(n+1); rep(i,n)w.set(i,a[i]+mx); w.build(); ll ans=0; repd(i,1,n+1){ vec l(n/i+1),r(n/i+1); rep(j,n/i){ ll x=j*i; ll y=x+i; l[j+1]=w.kth_smallest(x,y,(i-1)/2)-mx; y=n-j*i; x=y-i; r[j+1]=w.kth_smallest(x,y,(i-1)/2)-mx; l[j+1]+=l[j]; r[j+1]+=r[j]; } multiset<ll> s; rep(j,n/i+1){ s.insert(l[j]); } rep(j,n/i+1){ ll now=r[j]; now+=*s.rbegin(); s.erase(s.lower_bound(l[n/i-j])); now*=i; chmax(ans,now); } } cout<<ans<<endl; return 0; }