結果

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

ソースコード

diff #
raw source code 

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

// vector<vector<bool>> dp
bool possible(vector<long long> v, long long mid){
    for(long long i = 0; i < v.size(); i++){
        v[i] = v[i] + (i + 1)*mid;
    }
    for (long long i = 1; i < v.size(); i++)
    {
        if(v[i] <= v[i-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(long long i = 0; i < n; i++){

            cin >> a[i];
        }
        long long low = 0;
        long long high = n;
        long long ans = high;
        while(low <= high){
            long long mid = low + (high-low)/2;
            if(possible(a,mid)){
                ans = high;
                high = mid - 1;

            }else{
                low = mid + 1;
            }
        }
        cout << ans << endl;
    }
}
0