結果

問題 No.3129 Multiple of Twin Subarray
ユーザー iomir
提出日時 2025-04-25 22:52:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 239 ms / 2,000 ms
コード長 4,313 bytes
コンパイル時間 3,690 ms
コンパイル使用メモリ 283,820 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2025-04-25 22:52:23
合計ジャッジ時間 11,758 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

#define all(v) v.begin(),v.end()
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using vll=vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,ll>;
using vp=vector<pair<ll, ll>>;
//using mint=modint1000000007;
//using mint=modint998244353;

const ll INF=1ll<<60;
ll mod10=1e9+7;
ll mod99=998244353;
const double PI = acos(-1);

#define rep(i,n) for (ll i=0;i<n;++i)
#define per(i,n) for(ll i=n-1;i>=0;--i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
#define per2(i,a,n) for (ll i=a;i>=n;--i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

template<typename monoid>
struct segtree{
    using T = typename monoid::Type;
    ll N;
    vector<T> node;
    segtree(ll n){
        N=1;
        while(N<n) N*=2;
        node = vector<T>(N*2-1,monoid::id());
    }
    T operator [](int k){
        return node[N-1+k];
    }
    void update(int k,T x){
        k+=N-1;
        node[k]=x;
        while(k){
            k=(k-1)/2;
            node[k]=monoid::op(node[2*k+1],node[2*k+2]);
        }
    }
    T query(int a,int b,int k,int l,int r){
        if(r<=a||b<=l) return monoid::id();
        else if(a<=l&&r<=b) return node[k];
        else{
            int m=(l+r)/2;
            return monoid::op(query(a,b,2*k+1,l,m),query(a,b,2*k+2,m,r));
        }
    }
    T sub(int a,int b){
        return query(a,b,0,0,N);
    }

    int max_right_sub(ll a,ll b,auto f2){return max_right(a,b,0,0,N,f2,monoid::id()).second;}
    pair<T,ll> max_right(ll a,ll b,ll k,ll l,ll r,auto f2,T v){
        if(r<=a||b<=l){
            return {monoid::id(),-1};
        }else if(a<=l&&r<=b&&(!f2(monoid::op(node[k],v)))){
            return {node[k],-1};
        }else if(k>=N-1){
            return (f2(monoid::op(v,node[k]))?make_pair(node[k],k-(N-1)):make_pair(node[k],-1ll));
        }else{
            auto[vr,ir] = max_right(a,b,2*k+2,(l+r)/2,r,f2,v);
            if(ir!=-1){
                return {vr,ir};
            }else{
                auto [vl,il]= max_right(a,b,2*k+1,l,(l+r)/2,f2,monoid::op(v,vr));
                return {vl,il};
            }
        }
    }

    int min_left_sub(ll a,ll b,auto f2){return min_left(a,b,0,0,N,f2,monoid::id()).second;}
    pair<T,ll> min_left(ll a,ll b,ll k,ll l,ll r,auto f2,T v){
        if(r<=a||b<=l){
            return {monoid::id(),N+1};
        }else if(a<=l&&r<=b&&(!f2(monoid::op(node[k],v)))){
           return {node[k],N+1};
        }else if(k>=N-1){
            return (f2(monoid::op(v,node[k]))?make_pair(node[k],k-(N-1)):make_pair(node[k],N+1));
        }else{
            auto [vl,il] = min_left(a,b,2*k+1,l,(l+r)/2,f2,v);
            if(il!=N+1){
                return {vl,il};
            }else{
                auto [vr,ir]=min_left(a,b,2*k+2,(l+r)/2,r,f2,monoid::op(v,vl));
                return {vr,ir};
            }
        }
    }
};

struct monoid{
    using Type = long long;
    static Type op(Type a,Type b){
       return max(a,b);
    }
    static Type id(){return -INF;}
};

struct monoid2{
    using Type = long long;
    static Type op(Type a,Type b){
       return min(a,b);
    }
    static Type id(){return INF;}
};


bool solve(){
    ll N;cin>>N;
    vll A(N);rep(i,N) cin>>A[i];
    vll rw(N+1);rep(i,N) rw[i+1]=rw[i]+A[i];
    ll ans=-INF;
    segtree<monoid> segl(N+1),segr(N+1);
  
    ll mi=0;
    rep2(r,1,N+1){
        segr.update(r,rw[r]-mi);
        chmin(mi,rw[r]);
    }
    
    ll ma=rw[N];
    for(int i=N-1;i>=0;i--){
        segl.update(i,ma-rw[i]);
        chmax(ma,rw[i]);
    }

    rep2(i,1,N){
        chmax(ans,segr.sub(1,i+1)*segl.sub(i,N));
    }


    segtree<monoid2> segl2(N+1),segr2(N+1);
    mi=0;
    rep2(r,1,N+1){
        segr2.update(r,rw[r]-mi);
        chmax(mi,rw[r]);
    }
    
    ma=rw[N];
    for(int i=N-1;i>=0;i--){
        segl2.update(i,ma-rw[i]);
        chmin(ma,rw[i]);
    }

    rep2(i,1,N){
        chmax(ans,segr2.sub(1,i+1)*segl2.sub(i,N));
    }








    cout << ans << endl;
    return 0;
}




int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll T=1;//cin>>T;
    rep(i,T) solve();
}
0