結果
問題 | No.919 You Are A Project Manager |
ユーザー | polyomino_24 |
提出日時 | 2019-10-26 00:33:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 115 ms / 3,000 ms |
コード長 | 9,003 bytes |
コンパイル時間 | 1,364 ms |
コンパイル使用メモリ | 134,244 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-27 17:40:08 |
合計ジャッジ時間 | 5,860 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
6,816 KB |
testcase_01 | AC | 5 ms
6,944 KB |
testcase_02 | AC | 5 ms
6,940 KB |
testcase_03 | AC | 5 ms
6,940 KB |
testcase_04 | AC | 20 ms
6,944 KB |
testcase_05 | AC | 22 ms
6,940 KB |
testcase_06 | AC | 6 ms
6,944 KB |
testcase_07 | AC | 46 ms
6,940 KB |
testcase_08 | AC | 14 ms
6,940 KB |
testcase_09 | AC | 11 ms
6,940 KB |
testcase_10 | AC | 17 ms
6,940 KB |
testcase_11 | AC | 16 ms
6,944 KB |
testcase_12 | AC | 5 ms
6,944 KB |
testcase_13 | AC | 20 ms
6,944 KB |
testcase_14 | AC | 6 ms
6,944 KB |
testcase_15 | AC | 9 ms
6,944 KB |
testcase_16 | AC | 27 ms
6,944 KB |
testcase_17 | AC | 77 ms
6,944 KB |
testcase_18 | AC | 77 ms
6,940 KB |
testcase_19 | AC | 79 ms
6,940 KB |
testcase_20 | AC | 105 ms
6,944 KB |
testcase_21 | AC | 78 ms
6,944 KB |
testcase_22 | AC | 50 ms
6,944 KB |
testcase_23 | AC | 48 ms
6,940 KB |
testcase_24 | AC | 52 ms
6,940 KB |
testcase_25 | AC | 49 ms
6,944 KB |
testcase_26 | AC | 101 ms
6,940 KB |
testcase_27 | AC | 90 ms
6,940 KB |
testcase_28 | AC | 112 ms
6,940 KB |
testcase_29 | AC | 77 ms
6,944 KB |
testcase_30 | AC | 78 ms
6,940 KB |
testcase_31 | AC | 78 ms
6,940 KB |
testcase_32 | AC | 78 ms
6,940 KB |
testcase_33 | AC | 55 ms
6,940 KB |
testcase_34 | AC | 54 ms
6,948 KB |
testcase_35 | AC | 114 ms
6,940 KB |
testcase_36 | AC | 115 ms
6,944 KB |
testcase_37 | AC | 114 ms
6,944 KB |
testcase_38 | AC | 112 ms
6,940 KB |
testcase_39 | AC | 5 ms
6,944 KB |
testcase_40 | AC | 9 ms
6,944 KB |
testcase_41 | AC | 6 ms
6,940 KB |
testcase_42 | AC | 6 ms
6,944 KB |
testcase_43 | AC | 8 ms
6,940 KB |
testcase_44 | AC | 11 ms
6,940 KB |
testcase_45 | AC | 6 ms
6,940 KB |
testcase_46 | AC | 10 ms
6,940 KB |
testcase_47 | AC | 50 ms
6,940 KB |
testcase_48 | AC | 50 ms
6,940 KB |
testcase_49 | AC | 53 ms
6,940 KB |
testcase_50 | AC | 49 ms
6,944 KB |
testcase_51 | AC | 46 ms
6,940 KB |
testcase_52 | AC | 37 ms
6,944 KB |
testcase_53 | AC | 46 ms
6,944 KB |
testcase_54 | AC | 9 ms
6,940 KB |
testcase_55 | AC | 5 ms
6,944 KB |
testcase_56 | AC | 5 ms
6,940 KB |
testcase_57 | AC | 5 ms
6,944 KB |
ソースコード
#include <algorithm> #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <tuple> #include <vector> #include <list> #define rep(i, n) for (int i = 0; i < (int)(n); ++i) //#define cerr if(false) cerr #ifdef DEBUG #define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__); #else #define show(...) 42 #endif using namespace std; using ll = long long; using pii = pair<int, int>; template <typename T, typename S> ostream& operator<<(ostream& os, pair<T, S> a) { os << '(' << a.first << ',' << a.second << ')'; return os; } template <typename T> ostream& operator<<(ostream& os, vector<T> v) { for (auto x : v) os << x << ' '; return os; } void debug() { cerr << '\n'; } template <typename H, typename... T> void debug(H a, T... b) { cerr << a; if (sizeof...(b)) cerr << ", "; debug(b...); } template<int N> class FID { static const int bucket = 512, block = 16; static char popcount[]; int n, B[N/bucket+10]; unsigned short bs[N/block+10], b[N/block+10]; public: FID(){} FID(int n, bool s[]) : n(n) { if(!popcount[1]) for (int i = 0; i < (1<<block); i++) popcount[i] = __builtin_popcount(i); bs[0] = B[0] = b[0] = 0; for (int i = 0; i < n; i++) { if(i%block == 0) { bs[i/block+1] = 0; if(i%bucket == 0) { B[i/bucket+1] = B[i/bucket]; b[i/block+1] = b[i/block] = 0; } else b[i/block+1] = b[i/block]; } bs[i/block] |= short(s[i])<<(i%block); b[i/block+1] += s[i]; B[i/bucket+1] += s[i]; } if(n%bucket == 0) b[n/block] = 0; } // number of val in [0,r), O(1) int count(bool val, int r) { return val? B[r/bucket]+b[r/block]+popcount[bs[r/block]&((1<<(r%block))-1)]: r-count(1,r); } // number of val in [l,r), O(1) int count(bool val, int l, int r) { return count(val,r)-count(val,l); } // position of ith in val, 0-indexed, O(log n) int select(bool val, int i) { if(i < 0 or count(val,n) <= i) return -1; i++; int lb = 0, ub = n, md; while(ub-lb>1) { md = (lb+ub)>>1; if(count(val,md) >= i) ub = md; else lb = md; } return ub-1; } int select(bool val, int i, int l) { return select(val,i+count(val,l)); } bool operator[](int i) { return bs[i/block]>>(i%block)&1; } }; template<int N> char FID<N>::popcount[1<<FID<N>::block]; template<class T, int N, int D> class wavelet { int n, zs[D]; FID<N> dat[D]; void max_dfs(int d, int l, int r, int &k, T val, vector<T> &vs) { if(l >= r or !k) return; if(d == D) { while(l++ < r and k > 0) vs.push_back(val), k--; return; } int lc = dat[d].count(1,l), rc = dat[d].count(1,r); // if min, change this order max_dfs(d+1, lc+zs[d], rc+zs[d], k, 1ULL<<(D-d-1)|val,vs); max_dfs(d+1, l-lc, r-rc, k, val, vs); } T max_dfs(int d, int l, int r, T val, T a, T b) { if(r-l <= 0 or val >= b) return -1; if(d == D) return val>=a? val: -1; int lc = dat[d].count(1,l), rc = dat[d].count(1,r); T ret = max_dfs(d+1, lc+zs[d], rc+zs[d], 1ULL<<(D-d-1)|val, a, b); if(~ret) return ret; return max_dfs(d+1, l-lc, r-rc, val, a, b); } int freq_dfs(int d, int l, int r, T val, T a, T b) { if(l == r) return 0; if(d == D) return (a <= val and val < b)? r-l: 0; T nv = 1ULL<<(D-d-1)|val, nnv = ((1ULL<<(D-d-1))-1)|nv; if(nnv < a or b <= val) return 0; if(a <= val and nnv < b) return r-l; int lc = dat[d].count(1,l), rc = dat[d].count(1,r); return freq_dfs(d+1,l-lc,r-rc,val,a,b)+ freq_dfs(d+1,lc+zs[d],rc+zs[d],nv,a,b); } void list_dfs(int d, int l, int r, T val, T a, T b, vector<pair<T,int>> &vs) { if(val >= b or r-l <= 0) return; if(d == D) { if(a <= val) vs.push_back(make_pair(val,r-l)); return; } T nv = val|(1LL<<(D-d-1)), nnv = nv|(((1LL<<(D-d-1))-1)); if(nnv < a) return; int lc = dat[d].count(1,l), rc = dat[d].count(1,r); list_dfs(d+1,l-lc,r-rc,val,a,b,vs); list_dfs(d+1,lc+zs[d],rc+zs[d],nv,a,b,vs); } public: wavelet(int n, T seq[]) : n(n) { T f[N], l[N], r[N]; bool b[N]; memcpy(f, seq, sizeof(T)*n); for (int d = 0; d < D; d++) { int lh = 0, rh = 0; for (int i = 0; i < n; i++) { bool k = (f[i]>>(D-d-1))&1; if(k) r[rh++] = f[i]; else l[lh++] = f[i]; b[i] = k; } dat[d] = FID<N>(n,b); zs[d] = lh; swap(l,f); memcpy(f+lh, r, rh*sizeof(T)); } } T get(int i) { T ret = 0; bool b; for (int d = 0; d < D; d++) { ret <<= 1; b = dat[d][i]; ret |= b; i = dat[d].count(b,i)+b*zs[d]; } return ret; } T operator[](int i) { return get(i); } int count(T val, int l, int r) { for (int d = 0; d < D; d++) { bool b = (val>>(D-d-1))&1; l = dat[d].count(b,l)+b*zs[d]; r = dat[d].count(b,r)+b*zs[d]; } return r-l; } int count(T val, int r) { return count(val,0,r); } int select(T val, int k) { int ls[D], rs[D], l = 0, r = n; for (int d = 0; d < D; d++) { ls[d] = l; rs[d] = r; bool b = val>>(D-d-1)&1; l = dat[d].count(b,l)+b*zs[d]; r = dat[d].count(b,r)+b*zs[d]; } for (int d = D-1; d >= 0; d--) { bool b = val>>(D-d-1)&1; k = dat[d].select(b,k,ls[d]); if(k >= rs[d] or k < 0) return -1; k -= ls[d]; } return k; } int select(T val, int k, int l) { return select(val,k+count(val,l)); } vector<T> maximum(int l, int r, int k) { if (r-l < k) k = r-l; if(k < 0) return {}; vector<T> ret; max_dfs(0,l,r,k,0,ret); return ret; } T maximum(int l, int r, T a, T b) { return max_dfs(0,l,r,0,a,b); } // k is 0-indexed T kth_number(int l, int r, int k) { if(r-l <= k or k < 0) return -1; T ret = 0; for (int d = 0; d < D; d++) { int lc = dat[d].count(1,l), rc = dat[d].count(1,r); if(rc-lc > k) { l = lc+zs[d]; r = rc+zs[d]; ret |= 1ULL<<(D-d-1); } else { k -= rc-lc; l -= lc; r -= rc; } } return ret; } vector<pair<T,int>> freq_list(int l, int r, T a, T b) { vector<pair<T,int>> ret; list_dfs(0,l,r,0,a,b,ret); return ret; } vector<pair<int,T>> get_rect(int l, int r, T a, T b) { vector<pair<T,int>> res = freq_list(l,r,a,b); vector<pair<int,T>> ret; for(auto &e: res) for (int i = 0; i < e.second; i++) ret.push_back(make_pair(select(e.first,i,l), e.first)); return ret; } // number of elements in [l,r) in [a,b), O(D) int freq(int l, int r, T a, T b) { return freq_dfs(0,l,r,0,a,b); } }; const int N = 100100, D = 31; int a[N]; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; const int offset = 1e9; rep(i,n)cin >> a[i]; rep(i,n)a[i] += offset; wavelet<int, N, D> wm(n,a); ll ans = -(1LL<<60); for(int k = 1; k <= n; k++){ ll sum = 0; const int pos = k - 1 -(k - 1)/ 2; show(pos); vector<ll> dp[2]; for(int i = 0; i + k <= n; i+= k){ show(wm.kth_number(i, i + k, pos)-offset); dp[0].push_back((ll)k * (wm.kth_number(i, i + k, pos) - offset)); } for(int i = n; i - k >= 0; i-= k){ dp[1].push_back((ll)k * (wm.kth_number(i - k, i, pos) - offset)); } show(dp[0],dp[1]); const int sz = (int) dp[0].size(); rep(i,2){ sum = max(sum,dp[i][0]); rep(j,sz-1){ dp[i][j+1] += dp[i][j]; sum = max(sum, dp[i][j+1]); } } vector<ll> rui(sz); rep(i,sz){ if(i==0)rui[i] = dp[0][0]; else rui[i] = max(rui[i-1], dp[0][i]); } rep(i,sz-1){ sum = max(sum, rui[i] + dp[1][sz - 2 -i]); } show(k, sz, sum); ans = max(ans, sum); } cout << ans << endl; }