結果

問題 No.3129 Multiple of Twin Subarray
コンテスト
ユーザー アンペア券
提出日時 2025-04-25 23:20:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,152 bytes
コンパイル時間 2,351 ms
コンパイル使用メモリ 197,908 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2025-04-25 23:20:45
合計ジャッジ時間 6,488 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 43 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef __LOCAL
#define _GLIBCXX_DEBUG
#include "debug2.h"
#endif
#ifndef __LOCAL
#define show(...) 
#define SET_GROUP(x)
#define SET_MAXCNT(x)
#endif

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//#include <boost/multiprecision/cpp_int.hpp>
//using bigint = boost::multiprecision::cpp_int;
#define SIZE(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
using ll = long long;
//int di[] = {1, 0, -1, 0, 1, -1, -1, 1};
//int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T>bool chmin(T& x,T y){if(x>y){x=y;return true;}return false;}
template<class T>bool chmax(T& x,T y){if(x<y){x=y;return true;}return false;}
template<class T>vector<T>matrix(int n1,T val){return vector<T>(n1,val);}
template<class T>vector<vector<T>>matrix(int n1,int n2,T val){return vector<vector<T>>(n1,matrix<T>(n2,val));}
template<class T>vector<vector<vector<T>>>matrix(int n1,int n2,int n3,T val){return vector<vector<vector<T>>>(n1,matrix<T>(n2,n3,val));}
template<class T>vector<vector<vector<vector<T>>>>matrix(int n1,int n2,int n3,int n4,T val){return vector<vector<vector<vector<T>>>>(n1,matrix<T>(n2,n3,n4,val));}
template<class T>T sum(vector<T>x){T r=0;for(auto e:x)r+=e;return r;}
template<class T>T max(vector<T>x){T r=x[0];for(auto e:x)chmax(r,e);return r;}
template<class T>T min(vector<T>x){T r=x[0];for(auto e:x)chmin(r,e);return r;}
template<class T>set<T>toSet(vector<T>x){set<T> r;for(auto e:x)r.emplace(e);return r;}
template<class T>map<T,ll>toMap(vector<T>x){map<T,ll>mp;for(auto e:x)mp[e]++;return mp;}
template<class T>vector<T>toVector(set<T>x){vector<T> r;for(auto e:x)r.push_back(e);return r;}
template<class T1,class T2>pair<T1,T2> operator+(pair<T1,T2>x,pair<T1,T2>y){return make_pair(x.first+y.first,x.second+y.second);}
template<class T1,class T2>pair<T1,T2> operator-(pair<T1,T2>x,pair<T1,T2>y){return make_pair(x.first-y.first,x.second-y.second);}
template<class T1,class T2>istream&operator>>(istream&is,tuple<T1,T2>&x){cin>>get<0>(x)>>get<1>(x);return is;}
template<class T1,class T2,class T3>istream&operator>>(istream&is,tuple<T1,T2,T3>&x){cin>>get<0>(x)>>get<1>(x)>>get<2>(x);return is;}
template<class T1,class T2>istream&operator>>(istream&is,pair<T1,T2>&x){cin>>x.first>>x.second;return is;}
template<class T>istream&operator>>(istream&is,vector<T>&x){for(auto&&e:x)is>>e;return is;}
template<class T>istream&operator>>(istream&is,vector<vector<T>>&x){for(auto&&e:x)for(auto&&f:e)is>>f;return is;}
template<class T>ostream&operator<<(ostream&os,const vector<T>&x){for(auto e:x)os<<e<<" ";return os;}
template<class T>ostream&operator<<(ostream&os,const vector<vector<T>>&x){for(auto e:x){for(auto f:e)os<<f<<" ";os<<"\n";}return os;}

ll inf = 1LL << 30;

ll solve(const vector<ll>& a){
    int n = SIZE(a);
    vector<ll> sumA(n + 1, 0), sumB(n + 1, 0);
    for(int i = 0; i < n; ++i){
        sumA[i + 1] = sumA[i] + a[i];
    }
    for(int i = n - 1; i >= 0; --i){
        sumB[i] = sumB[i + 1] + a[i];
    }
    
    vector<ll> preMin(n + 1, 0), backMin(n + 1, 0);
    vector<ll> preMin2(n + 1, 0), backMin2(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        chmin(preMin[i], min(sumA[i], preMin[i - 1]));
        preMin2[i] = sumA[i] - preMin[i - 1];
        chmax(preMin2[i], preMin2[i - 1]);
    }
    for(int i = n - 1; i >= 0; --i){
        chmin(backMin[i], min(sumB[i], backMin[i + 1]));
        backMin2[i] = sumB[i] - backMin[i + 1];
        chmax(backMin2[i], backMin2[i + 1]);
    }

    show(a);
    show(sumA);
    show(preMin);
    show(preMin2);
    show(sumB);
    show(backMin);
    show(backMin2);

    ll ans = -1LL << 60;
    for(int i = 1; i < n; ++i){
        ll maxFront = preMin2[i];
        ll maxBack = backMin2[i];
        ll tmpans = maxFront * maxBack;
        if(maxFront >= 0 && maxBack >= 0){
            chmax(ans, tmpans);
        }
        show(i, maxFront, maxBack, tmpans);
    }
    return ans;
}

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    cin >> a;

    ll ans = 0;
    chmax(ans, solve(a));
    for(auto&& e : a) e *= -1;
    show("----------");
    chmax(ans, solve(a));
    cout << ans << endl;
    return 0;
}
0