結果
問題 | No.919 You Are A Project Manager |
ユーザー | raven7959 |
提出日時 | 2022-03-01 23:51:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,516 ms / 3,000 ms |
コード長 | 10,847 bytes |
コンパイル時間 | 3,119 ms |
コンパイル使用メモリ | 248,780 KB |
実行使用メモリ | 25,316 KB |
最終ジャッジ日時 | 2024-07-08 07:09:03 |
合計ジャッジ時間 | 25,279 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 290 ms
23,528 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 40 ms
7,856 KB |
testcase_05 | AC | 42 ms
8,192 KB |
testcase_06 | AC | 10 ms
5,376 KB |
testcase_07 | AC | 387 ms
11,936 KB |
testcase_08 | AC | 103 ms
5,632 KB |
testcase_09 | AC | 65 ms
5,376 KB |
testcase_10 | AC | 75 ms
6,140 KB |
testcase_11 | AC | 71 ms
5,992 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 103 ms
6,784 KB |
testcase_14 | AC | 5 ms
5,376 KB |
testcase_15 | AC | 34 ms
5,376 KB |
testcase_16 | AC | 161 ms
8,064 KB |
testcase_17 | AC | 265 ms
23,616 KB |
testcase_18 | AC | 257 ms
23,652 KB |
testcase_19 | AC | 282 ms
23,652 KB |
testcase_20 | AC | 1,336 ms
23,312 KB |
testcase_21 | AC | 289 ms
23,656 KB |
testcase_22 | AC | 427 ms
12,608 KB |
testcase_23 | AC | 407 ms
12,472 KB |
testcase_24 | AC | 451 ms
13,000 KB |
testcase_25 | AC | 475 ms
12,612 KB |
testcase_26 | AC | 1,446 ms
22,912 KB |
testcase_27 | AC | 1,050 ms
20,640 KB |
testcase_28 | AC | 1,516 ms
24,780 KB |
testcase_29 | AC | 253 ms
23,656 KB |
testcase_30 | AC | 253 ms
23,660 KB |
testcase_31 | AC | 250 ms
23,656 KB |
testcase_32 | AC | 248 ms
23,652 KB |
testcase_33 | AC | 475 ms
13,540 KB |
testcase_34 | AC | 482 ms
13,544 KB |
testcase_35 | AC | 1,487 ms
25,192 KB |
testcase_36 | AC | 1,494 ms
25,316 KB |
testcase_37 | AC | 1,494 ms
25,196 KB |
testcase_38 | AC | 1,482 ms
25,196 KB |
testcase_39 | AC | 3 ms
5,376 KB |
testcase_40 | AC | 39 ms
5,376 KB |
testcase_41 | AC | 6 ms
5,376 KB |
testcase_42 | AC | 9 ms
5,376 KB |
testcase_43 | AC | 16 ms
5,376 KB |
testcase_44 | AC | 56 ms
5,376 KB |
testcase_45 | AC | 9 ms
5,376 KB |
testcase_46 | AC | 43 ms
5,376 KB |
testcase_47 | AC | 426 ms
12,740 KB |
testcase_48 | AC | 417 ms
12,604 KB |
testcase_49 | AC | 459 ms
13,140 KB |
testcase_50 | AC | 431 ms
12,600 KB |
testcase_51 | AC | 368 ms
11,668 KB |
testcase_52 | AC | 264 ms
9,984 KB |
testcase_53 | AC | 375 ms
11,800 KB |
testcase_54 | AC | 35 ms
5,376 KB |
testcase_55 | AC | 2 ms
5,376 KB |
testcase_56 | AC | 1 ms
5,376 KB |
testcase_57 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)#define all(x) (x).begin(), (x).end()#define sz(x) int(x.size())#define yn(joken) cout<<((joken) ? "Yes" : "No")<<endl#define YN(joken) cout<<((joken) ? "YES" : "NO")<<endlusing namespace std;using ll = long long;using vi = vector<int>;using vl = vector<ll>;using vs = vector<string>;using vc = vector<char>;using vd = vector<double>;using vvi = vector<vector<int>>;using vvl = vector<vector<ll>>;using vvd = vector<vector<double>>;const int INF = 1e9;const ll LINF = 1e18;template <class T>bool chmax(T& a, const T& b) {if (a < b) {a = b;return 1;}return 0;}template <class T>bool chmin(T& a, const T& b) {if (b < a) {a = b;return 1;}return 0;}template <class T>vector<T> make_vec(size_t a) {return vector<T>(a);}template <class T, class... Ts>auto make_vec(size_t a, Ts... ts) {return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}template <typename T>istream& operator>>(istream& is, vector<T>& v) {for (int i = 0; i < int(v.size()); i++) {is >> v[i];}return is;}template <typename T>ostream& operator<<(ostream& os, const vector<T>& v) {for (int i = 0; i < int(v.size()); i++) {os << v[i];if (i < int(v.size()) - 1) os << ' ';}return os;}// すでに追加したものを削除できるslope trick// Query query(): Query{lx,rx,min_f}を返す,[lx,rx]でmin_fを取る// add_all(T a): f(x)にaを加算する// add_a_minus_x(T a): f(x)にmax(a-x,0)を加算する, \_// add_x_minus_a(T a): f(x)にmax(x-a,0)を加算する, _/// add_abs(T a): f(x)に|x-a|を加算する, \/// erase_a_minus_x(T a): f(x)からmax(a-x,0)を削除する, \_// erase_x_minus_a(T a): f(x)からmax(x-a,0)を削除する, _/// erase_abs(T a): f(x)から|x-a|を削除する, \/// clear_right(): f(x)<-min(f(t)),t<=x , \_/ -> \_// clear_left(): f(x)<-min(f(t)),x<=t , \_/ -> _/// shift(T a,T b): f(x)<-min(f(t)),x-b<=t<=x-a// shift(T a): f(x)<-f(x-a),shift(a,a)してるだけ// get(T x): f(x)を返す, fを破壊しO(sz(L)+sz(R))// merge(SlopeTrick x): f(x)にg(x)を加算する, gを破壊するtemplate <typename T>struct ErasableSlopeTrick{const T INF = numeric_limits<T>::max() / 3;set<T> S_l,S_r;map<T,T> mp_l,mp_r;T min_f, offset_l, offset_r;private:void insert_R(const T &a){S_r.insert(a - offset_r);mp_r[a - offset_r]++;}T top_R() const{if (S_r.empty()) return INF;else return *S_r.begin() + offset_r;}T pop_R(){T val = top_R();if (!S_r.empty()){mp_r[val]--;if(mp_r[val]==0) S_r.erase(val);}return val;}void insert_L(const T &a){S_l.insert(a - offset_l);mp_l[a - offset_l]++;}T top_L() const{if (S_l.empty()) return -INF;else return *--S_l.end() + offset_l;}T pop_L(){T val = top_L();if (!S_l.empty()){mp_l[val]--;if(mp_l[val]==0) S_l.erase(val);}return val;}size_t size(){return S_l.size() + S_r.size();}public:ErasableSlopeTrick() : min_f(0), offset_l(0), offset_r(0) {}struct Query{T lx, rx, min_f;};Query query() const{return (Query){top_L(), top_R(), min_f};}void add_all(const T &a){min_f += a;}void add_a_minus_x(const T &a){insert_R(a);insert_L(pop_R());min_f += max(T(0), a - top_L());}void add_x_minus_a(const T &a){insert_L(a);insert_R(pop_L());min_f += max(T(0), top_R() - a);}void add_abs(const T &a){add_a_minus_x(a);add_x_minus_a(a);}void erase_a_minus_x(const T &a){if(S_l.find(a - offset_l)==S_l.end()){mp_r[a - offset_r]--;if(mp_r[a - offset_r]==0) S_r.erase(a - offset_r);insert_R(pop_L());}else{mp_l[a - offset_l]--;if(mp_l[a - offset_l]==0) S_l.erase(a - offset_l);}min_f -= max(T(0), a - top_R());}void erase_x_minus_a(const T &a){if(S_l.find(a - offset_l)==S_l.end()){mp_r[a - offset_r]--;if(mp_r[a - offset_r]==0) S_r.erase(a - offset_r);}else{mp_l[a - offset_l]--;if(mp_l[a- offset_l]==0) S_l.erase(a - offset_l);insert_L(pop_R());}min_f -= max(T(0), top_L() - a);}void erase_abs(const T &a){erase_a_minus_x(a);erase_x_minus_a(a);}void clear_right(){if(!S_r.empty()) S_r.clear();}void clear_left(){if(!S_l.empty()) S_l.clear();}void shift(const T &a, const T &b){assert(a <= b);offset_l += a;offset_r += b;}void shift(const T &a){shift(a, a);}T get(const T &x){T ret = min_f;while (!S_l.empty()) ret += max(T(0), pop_L() - x);while (!S_r.empty()) ret += max(T(0), x - pop_R());return ret;}void merge(ErasableSlopeTrick &st){if (st.size() > size()){swap(st.S_l, S_l);swap(st.S_r, S_r);swap(st.min_f, min_f);swap(st.offset_l, offset_l);swap(st.offset_r, offset_r);}while (!st.S_r.empty()) add_x_minus_a(st.pop_R());while (!st.S_l.empty()) add_a_minus_x(st.pop_L());min_f += st.min_f;}};// Mo(N): 扱う区間の幅のmax, 最適なバケットサイズを計算するのに使う// add(l,r): クエリの対象となる範囲として半開区間[l,r)を追加// build(add_left,add_right,erase_left,erase_right,out): 各種関数を渡す// add/erase_left/right: 左端/右端を1動かして要素を追加/削除する// out: クエリごとの答えが出たら、それを反映させるstruct Mo{int n;vector<pair<int, int>> lr;explicit Mo(int n) : n(n) {}void add(int l, int r){lr.emplace_back(l, r);}template <typename AL, typename AR, typename EL, typename ER, typename O>void build(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out){int q = (int)lr.size();// バケットサイズの理想は n*sqrt(q) だがsqrt(q)がでかすぎると0になっちゃうのでint bs;if(q<=10000) bs = n / min<int>(n, sqrt(q));else bs = n / (min<int>(n, sqrt(q))*5);vector<int> ord(q);iota(begin(ord), end(ord), 0);sort(begin(ord), end(ord), [&](int a, int b){int ablock = lr[a].first / bs, bblock = lr[b].first / bs;if (ablock != bblock)return ablock < bblock;return (ablock & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second;});// 今,半開区間[l,r)をfoldしてますよ(のはず)int l = 0, r = 0;for (auto idx : ord){while (l > lr[idx].first) add_left(--l);while (r < lr[idx].second) add_right(r++);while (l < lr[idx].first) erase_left(l++);while (r > lr[idx].second) erase_right(--r);out(idx);}}template <typename A, typename E, typename O>void build(const A &add, const E &erase, const O &out){build(add, add, erase, erase, out);}};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int N;cin>>N;vl A(N);cin>>A;ll sm=0;for(int i=1;i<=N;i++) sm+=N/i;set<ll> S1,S2;int cnt1=0,cnt2=0;S1.insert(-LINF);S2.insert(LINF);map<ll,ll> mp1,mp2;map<int,pair<int,int>> idx1;vector<map<int,ll>> V1(N),V2(N);auto add_left=[&](int p){ll x=A[p];if(x<=*--S1.end()){S1.insert(x);mp1[x]++;cnt1++;}else{S2.insert(x);mp2[x]++;cnt2++;}while(cnt1>=cnt2+2){auto M=*--S1.end();mp1[M]--;if(mp1[M]==0) S1.erase(M);cnt1--;S2.insert(M);mp2[M]++;cnt2++;}while(cnt1<cnt2){auto m=*S2.begin();mp2[m]--;if(mp2[m]==0) S2.erase(m);cnt2--;S1.insert(m);mp1[m]++;cnt1++;}};auto erase_left=[&](int p){auto x=A[p];if(S1.find(x)==S1.end()){mp2[x]--;if(mp2[x]==0) S2.erase(x);cnt2--;}else{mp1[x]--;if(mp1[x]==0) S1.erase(x);cnt1--;}while(cnt1>=cnt2+2){auto M=*--S1.end();mp1[M]--;if(mp1[M]==0) S1.erase(M);cnt1--;S2.insert(M);mp2[M]++;cnt2++;}while(cnt1<cnt2){auto m=*S2.begin();mp2[m]--;if(mp2[m]==0) S2.erase(m);cnt2--;S1.insert(m);mp1[m]++;cnt1++;}};auto out=[&](int idx){auto P=idx1[idx];int i=P.first,j=P.second;V1[i-1][j]=*--S1.end();};Mo MA1(sm);int cnt=0;for(int i=1;i<=N;i++){for(int j=0;(j+1)*i<=N;j++){MA1.add(j*i,(j+1)*i);idx1[cnt]=make_pair(i,j);cnt++;}}MA1.build(add_left,erase_left,out);reverse(all(A));S1.clear();S2.clear();S1.insert(-LINF);S2.insert(LINF);cnt1=0;cnt2=0;mp1.clear();mp2.clear();auto out2=[&](int idx){auto P=idx1[idx];int i=P.first,j=P.second;V2[i-1][j]=*--S1.end();};Mo MA2(sm);for(int i=1;i<=N;i++){for(int j=0;(j+1)*i<=N;j++){MA2.add(j*i,(j+1)*i);}}MA2.build(add_left,erase_left,out2);ll ans=0;rep(i,N){rep(j,sz(V1[i])-1) V1[i][j+1]+=V1[i][j];}rep(i,N){rep(j,sz(V1[i])-1) chmax(V1[i][j+1],V1[i][j]);}rep(i,N){rep(j,sz(V2[i])-1) V2[i][j+1]+=V2[i][j];}rep(i,N){rep(j,sz(V2[i])-1) chmax(V2[i][j+1],V2[i][j]);}rep(i,N){rep(j,sz(V1[i])+1){ll tmp=0;if(j!=0) tmp+=V1[i][j-1];if(j!=sz(V1[i])) tmp+=V2[i][sz(V1[i])-j-1];chmax(ans,tmp*(i+1));}}cout<<ans<<endl;}