結果

問題 No.1467 Selling Cars
コンテスト
ユーザー Kanten4205
提出日時 2025-11-20 02:57:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,872 bytes
コンパイル時間 1,408 ms
コンパイル使用メモリ 97,868 KB
実行使用メモリ 19,408 KB
最終ジャッジ日時 2025-11-20 02:57:23
合計ジャッジ時間 12,431 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 巨大な数 (無限大として扱う)
const long long INF = 1e18;

// グローバル変数として入力を保持
int M, N;
vector<long long> A, B;
vector<long long> ans;

// 高速なスライド最小値のための手動リングバッファ (std::dequeは遅いため)
struct FastDeque {
    vector<int> q_idx;
    vector<long long> q_val;
    int head, tail;

    FastDeque(int size) {
        q_idx.resize(size);
        q_val.resize(size);
        head = 0;
        tail = 0;
    }

    inline void clear() {
        head = 0;
        tail = 0;
    }

    inline bool empty() {
        return head == tail;
    }

    inline void push_back(int idx, long long val) {
        q_idx[tail] = idx;
        q_val[tail] = val;
        tail++;
    }

    inline void pop_back() {
        tail--;
    }

    inline void pop_front() {
        head++;
    }

    inline long long back_val() {
        return q_val[tail - 1];
    }

    inline int front_idx() {
        return q_idx[head];
    }

    inline long long front_val() {
        return q_val[head];
    }
};

// 容量 k を固定したときの最小コストを計算する関数
// 計算量: O(MN)
long long calc(int k) {
    if (k <= 0) return INF;
    if (k > M) k = M; 

    // dp[i] : Aの先頭i個をマッチングさせた最小コスト
    // メモリ節約のため1次元配列を使い回す (prev -> curr)
    vector<long long> dp(M + 1, INF);
    dp[0] = 0;

    // DP遷移用バッファ
    vector<long long> next_dp(M + 1);
    
    // Dequeの初期化
    static FastDeque dq(M + 5);

    // Bの各要素についてループ (O(N))
    for (int j = 0; j < N; ++j) {
        long long b_val = B[j];
        dq.clear();
        
        // Aとの距離の累積和
        long long current_S = 0; 

        // Aの各要素についてスライド最小値 (O(M))
        for (int x = 0; x <= M; ++x) {
            // S[x] の更新: sum(|A[p] - b_val|)
            long long dist = (x > 0) ? abs(A[x-1] - b_val) : 0;
            current_S += dist;
            
            // 遷移式: next_dp[x] = S[x] + min(dp[y] - S[y])
            // 範囲: x - k <= y <= x

            // 1. 現在の dp[x] - S[x] を Deque に追加 (最小値を維持)
            if (dp[x] != INF) {
                long long val = dp[x] - current_S;
                while (!dq.empty() && dq.back_val() >= val) {
                    dq.pop_back();
                }
                dq.push_back(x, val);
            }
            
            // 2. ウィンドウ範囲外 (index < x - k) を削除
            if (!dq.empty() && dq.front_idx() < x - k) {
                dq.pop_front();
            }
            
            // 3. 最小値を使って next_dp[x] を更新
            if (!dq.empty()) {
                next_dp[x] = current_S + dq.front_val();
            } else {
                next_dp[x] = INF;
            }
        }
        // 配列の更新
        dp = next_dp;
    }
    return dp[M];
}

// 分割統治による解の埋め込み
// 範囲 [l, r] の答えを計算する。ans[l], ans[r] は既に計算済みとする。
void solve_dc(int l, int r) {
    if (l + 1 >= r) return;

    int mid = (l + r) / 2;
    
    // 中点の値を計算
    ans[mid] = calc(mid);

    // 凸性チェック: (l, mid, r) が一直線上にあるか？
    // (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1)
    // 注意: オーバーフローに気をつけるが、制約上 long long で足りる
    long long dy1 = ans[mid] - ans[l];
    long long dx1 = mid - l;
    long long dy2 = ans[r] - ans[mid];
    long long dx2 = r - mid;

    if (dy1 * dx2 == dy2 * dx1) {
        // 一直線上にある場合、間の値も線形補間できるため再帰しない
        // 直線の傾き
        long long slope = dy1 / dx1; // 割り切れるはず
        for (int i = l + 1; i < r; ++i) {
            if (i == mid) continue;
            ans[i] = ans[l] + slope * (long long)(i - l);
        }
    } else {
        // 直線でない場合は分割して再帰
        solve_dc(l, mid);
        solve_dc(mid, r);
    }
}

int main() {
    // 入出力高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    A.resize(M);
    for (int i = 0; i < M; ++i) cin >> A[i];
    B.resize(N);
    for (int i = 0; i < N; ++i) cin >> B[i];

    // ソート (必須)
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    ans.resize(M + 1);

    // 両端の計算
    ans[1] = calc(1);
    ans[M] = calc(M);

    // 分割統治開始
    solve_dc(1, M);

    // 出力
    for (int i = 1; i <= M; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}
0