結果

問題 No.2648 [Cherry 6th Tune D] 一次元の馬
コンテスト
ユーザー vjudge1
提出日時 2026-01-10 18:20:22
言語 C++17(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,008 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 818 ms
コンパイル使用メモリ 96,804 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-10 18:20:29
合計ジャッジ時間 6,654 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// vector<vector<bool>> dp
bool possible(const vector<long long> &a, long long mid)
{
    vector<long long> v = a;
    for (long long i = 0; i < v.size(); i++)
    {
        v[i] += (i + 1) * mid;
    }
    for (long long i = 1; i < v.size(); i++)
    {
        if (v[i] < v[i - 1] + 1)
            return false;
    }
    return true;
}

int main()
{
    long long t;
    cin >> t;
    while (t--)
    {
        long long n;
        cin >> n;
        vector<long long> a(n);
        for (auto &x : a)
            cin >> x;

        long long low = 0, high = 1e18, ans = 0;

        while (low <= high)
        {
            long long mid = low + (high - low) / 2;
            if (possible(a, mid))
            {
                ans = mid;
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        cout << ans << '\n';
    }
}
0