結果

問題 No.3129 Multiple of Twin Subarray
ユーザー arrsty217
提出日時 2025-04-26 01:26:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 77 ms / 2,000 ms
コード長 1,276 bytes
コンパイル時間 4,663 ms
コンパイル使用メモリ 279,964 KB
実行使用メモリ 11,096 KB
最終ジャッジ日時 2025-04-26 01:26:30
合計ジャッジ時間 7,542 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
using lli=long long int;
using vl=vector<lli>;
#define rep(i,s,e) for(lli i=s;i<e;i++)
#define rrep(i,s,e) for(int i=s-1;i>=e;i--)
#define vecl(v,s) vl v(s); rep(i,0,s) cin >> v.at(i);
using pll=pair<lli,lli>;
#define mp(f,s) make_pair(f,s)
#define fi first
#define se second
using vpll=vector<pll>;
#define vecpll(v,s) vpll v(s); rep(i,0,s) cin >> v.at(i).fi >> v.at(i).se;
#define print(s) cout << s << endl;
const lli LL_INF=1ll<<60;

int main() {
  int n; cin >> n;
  vecl(a,n);

  // l...[1,i] r...[i,N]
  // {max,min}
  vpll l(n+1),r(n+2);
  l[0]=mp(-LL_INF,LL_INF);
  l[1]=mp(a[0],a[0]);
  lli csum=a[0],cmin=min(a[0],0ll),cmax=max(a[0],0ll);
  rep(i,2,n+1){
    csum+=a[i-1];
    cmin=min(cmin,csum);
    cmax=max(cmax,csum);
    l[i]=mp(max(l[i-1].fi,csum-cmin),min(l[i-1].se,csum-cmax));
  }

  r[n+1]=mp(-LL_INF,LL_INF);
  r[n]=mp(a[n-1],a[n-1]);
  csum=a[n-1],cmin=min(a[n-1],0ll),cmax=max(a[n-1],0ll);
  rrep(i,n,1){
    csum+=a[i-1];
    cmin=min(cmin,csum);
    cmax=max(cmax,csum);
    r[i]=mp(max(r[i+1].fi,csum-cmin),min(r[i+1].se,csum-cmax));
  }

  lli ans=-LL_INF;
  rep(i,1,n){
    ans=max(ans,max(l[i].fi*r[i+1].fi,l[i].se*r[i+1].se));
  }
  print(ans);
}
0