結果

問題 No.3129 Multiple of Twin Subarray
コンテスト
ユーザー テナガザル
提出日時 2025-04-25 22:01:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 1,393 bytes
コンパイル時間 1,168 ms
コンパイル使用メモリ 105,708 KB
実行使用メモリ 13,440 KB
最終ジャッジ日時 2025-04-25 22:02:16
合計ジャッジ時間 4,793 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<long long> suml(n - 1), sumr(n - 1);
    suml[0] = a[0];
    sumr[n - 2] = a[n - 1];
    for (int i = 1; i < n - 1; ++i) suml[i] = suml[i - 1] + a[i];
    for (int i = n - 3; i >= 0; --i) sumr[i] = sumr[i + 1] + a[i + 1];
    vector<long long> mir(n), mil(n), mal(n), mar(n);
    mil[0] = suml[0];
    mal[0] = suml[0];
    mir[n - 2] = sumr[n - 2];
    mar[n - 2] = sumr[n - 2];
    long long ma = max(0LL, suml[0]), mi = min(0LL, suml[0]);
    for (int i = 1; i < n - 1; ++i)
    {
        mil[i] = min(suml[i] - ma, mil[i - 1]);
        mal[i] = max(suml[i] - mi, mal[i - 1]);
        ma = max(suml[i], ma);
        mi = min(suml[i], mi);
    }
    ma = max(0LL, sumr[n - 2]), mi = min(0LL, sumr[n - 2]);
    for (int i = n - 3; i >= 0; --i)
    {
        mir[i] = min(sumr[i] - ma, mir[i + 1]);
        mar[i] = max(sumr[i] - mi, mar[i + 1]);
        ma = max(sumr[i], ma);
        mi = min(sumr[i], mi);
    }
    long long ans = -1e18;
    for (int i = 0; i < n - 1; ++i)
    {
        ans = max(ans, mil[i] * mir[i]);
        ans = max(ans, mil[i] * mar[i]);
        ans = max(ans, mal[i] * mir[i]);
        ans = max(ans, mal[i] * mar[i]);
    }
    cout << ans << endl;
}
0