結果

問題 No.2221 Set X
コンテスト
ユーザー limbo
提出日時 2025-12-02 03:58:38
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,362 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,226 ms
コンパイル使用メモリ 204,528 KB
実行使用メモリ 16,208 KB
最終ジャッジ日時 2025-12-02 03:58:45
合計ジャッジ時間 7,256 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 3 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<long long> A(N);
    for (auto &x : A) cin >> x;

    long long D = A.back() - A[0];

    if (N == 1) {
        cout << 1 << " " << 2 << "\n";
        return 0;
    }

    long long limit = sqrt(D) + 5;
    vector<long long> Ws;

    // Case 1: small W
    for (long long W = 1; W <= limit; W++)
        Ws.push_back(W);

    // Case 2: approximately (D / (s-1)) for small s
    for (long long s = 2; s <= limit + 5; s++) {
        long long W = D / (s - 1);
        if (W >= 1)
            Ws.push_back(W);
    }

    // Case 1 segment (s=1)
    Ws.push_back(D + 1);

    sort(Ws.begin(), Ws.end());
    Ws.erase(unique(Ws.begin(), Ws.end()), Ws.end());

    long long bestW = -1, bestCost = LLONG_MAX;

    for (long long W : Ws) {
        long long segments = 1;
        long long cur = A[0] / W;

        for (int i = 1; i < N; i++) {
            long long s = A[i] / W;
            if (s != cur) {
                segments++;
                cur = s;
            }
        }

        long long cost = segments * (W + 1);

        if (cost < bestCost || (cost == bestCost && W < bestW)) {
            bestCost = cost;
            bestW = W;
        }
    }

    cout << bestW << "\n" << bestCost << "\n";
}
0