結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

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

    // Initialize with the cost for W=1 (Safe upper bound)
    // W=1 ensures min_total_mana <= 2*N
    long long best_W = 1;
    long long min_total_mana = -1; 

    // We only need to check W up to approximately 2*N.
    // Any W > 2*N would result in a base cost (W+1) > 2N + 1, 
    // which is strictly worse than the worst-case cost for W=1.
    long long limit = 2LL * N + 5; 

    for (long long W = 1; W <= limit; ++W) {
        long long segments = 0;
        long long current_mana = 0;
        int idx = 0;
        bool prune = false;

        // Calculate number of required segments for this width W
        while (idx < N) {
            segments++;
            
            // Calculate partial cost to check for pruning
            current_mana = segments * (W + 1);
            
            // Optimization: If current cost already exceeds or equals best found, 
            // this W cannot be the unique minimum or better than a smaller W.
            if (min_total_mana != -1 && current_mana >= min_total_mana) {
                prune = true;
                break;
            }

            // Determine the boundary of the current segment
            // The current projectile A[idx] is in the segment starting at floor(A[idx]/W)*W
            // The next segment starts at (floor(A[idx]/W) + 1) * W
            long long current_val = A[idx];
            long long segment_index = current_val / W;
            long long next_boundary = (segment_index + 1) * W;
            
            // Efficiently jump to the next projectile not covered by the current barrier
            auto it = lower_bound(A.begin() + idx, A.end(), next_boundary);
            idx = distance(A.begin(), it);
        }

        if (!prune) {
            // We found a new minimum cost
            // Strict inequality ensures we keep the smallest W in case of ties
            if (min_total_mana == -1 || current_mana < min_total_mana) {
                min_total_mana = current_mana;
                best_W = W;
            }
        }
    }

    cout << best_W << "\n";
    cout << min_total_mana << "\n";

    return 0;
}
0