結果

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

ソースコード

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);
        int flag = 0;
        for(long long i = 0; i < n; i++){
            
            cin >> a[i];
            if (i > 0 && a[i] <= a[i-1])
            {
                flag = 1;
            }
        }
        if(!flag){
            cout << 0 << endl;
        }else{

            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