結果

問題 No.2221 Set X
コンテスト
ユーザー limbo
提出日時 2025-12-02 03:56:10
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,511 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,755 ms
コンパイル使用メモリ 204,332 KB
実行使用メモリ 16,200 KB
最終ジャッジ日時 2025-12-02 03:56:18
合計ジャッジ時間 7,055 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 18 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 mn = A[0], mx = A.back();
    long long D = mx - mn;

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

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

    // 1) Small widths
    for (long long w = 1; w <= limit; w++)
        Ws.push_back(w);

    // 2) Breakpoints for floor(A/W)
    for (long long k = 1; k <= limit; k++) {
        long long L = D / (k + 1) + 1;
        long long R = D / k;
        if (L <= R) {
            if (L > limit) Ws.push_back(L);
            if (R > limit) Ws.push_back(R);
        }
    }

    // 3) MUST ADD W = D + 1 (one segment case)
    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 << " " << bestCost << "\n";
    return 0;
}
0