結果

問題 No.2221 Set X
コンテスト
ユーザー limbo
提出日時 2025-12-12 18:24:54
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 1,036 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,934 ms
コンパイル使用メモリ 197,260 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-12 18:25:00
合計ジャッジ時間 6,156 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){

    ll N; cin>>N;
    vector<ll> A(N);
    for(ll i=0; i<N; i++){
        cin>>A[i];
    }

    ll min_cost=2LL*N;
    ll best_X=1;

    for(ll X=2; X+1<min_cost; X++){
        ll current_segments=0;
        ll cost_overhead=X+1;
        bool pruned=0;

        for(ll i=0; i<N; ){
            current_segments++;
            if(current_segments*cost_overhead>=min_cost){
                pruned=true;
                break;
            }

            ll current_value=A[i];
            ll block_idx=current_value/X;

            ll next_block_start=(block_idx+1)*X;

            auto it= lower_bound(A.begin()+i+1,A.end(),next_block_start);
            i = distance(A.begin(),it);
        }

        if(!pruned){
            ll total_cost=current_segments*cost_overhead;
            if(total_cost<=min_cost){
                min_cost=total_cost;
                best_X=X;
            }
        }
    }

    cout<<best_X<<'\n'<<min_cost;


    return 0;
}
0