#1084197 (C++17) No.705 ゴミ拾い Hard

• 問題: No.705 ゴミ拾い Hard
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:24:45
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,009 bytes
• コンパイル時間: 1,320 ms
• コンパイル使用メモリ: 100,804 KB
• 実行使用メモリ: 15,096 KB
• 最終ジャッジ日時: 2025-05-14 13:25:47
• 合計ジャッジ時間: 5,172 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 4
other	AC * 18 WA * 22

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath> // For std::abs

// Using __int128_t for dp values and costs
using int128 = __int128_t;

// Helper to print __int128_t
std::ostream& operator<<(std::ostream& os, int128 val) {
    if (val == 0) {
        os << "0";
        return os;
    }
    std::string s = "";
    bool neg = false;
    if (val < 0) {
        neg = true;
        val = -val; 
    }
    while (val > 0) {
        s += (char)((val % 10) + '0'); // Explicit cast to char
        val /= 10;
    }
    if (neg) {
        s += '-';
    }
    std::reverse(s.begin(), s.end());
    os << s;
    return os;
}

int N_val;
std::vector<long long> A_vals, X_vals, Y_vals;
std::vector<int128> dp_vals;

// Using a large constant for infinity. Max possible sum is ~6e20.
// __int128 max is much larger (~1.7e38). This INF allows some additions.
const int128 INF = ((int128)1 << 120); 

// Function to calculate base^3 safely using int128
int128 power3(long long base) {
    int128 v = base; // Promote to int128 before multiplication
    return v * v * v;
}

// Cost for person p_idx to collect garbage starting at g_idx (0-indexed)
// The range collected is g_idx, ..., p_idx.
int128 calculate_cost_for_segment(int p_idx, int g_idx) {
    long long diff_x = A_vals[p_idx] - X_vals[g_idx];
    long long val_y = Y_vals[g_idx]; // Y_vals[g_idx] is non-negative as per constraints

    int128 term_x = power3(std::abs(diff_x));
    int128 term_y = power3(val_y);          

    return term_x + term_y;
}

void solve_dp(int p_low, int p_high, int k_opt_low, int k_opt_high) {
    if (p_low > p_high) {
        return;
    }

    int p_mid = p_low + (p_high - p_low) / 2;
    int best_k_for_pmid = -1; 
    // dp_vals[p_mid] is already INF. If it remains INF, best_k_for_pmid is not updated.
    // We need a valid best_k_for_pmid for recursive calls.
    // Initialize best_k_for_pmid to ensure it's within the valid range for k.
    // e.g. k_opt_low, or more restrictively current_k_search_low.
    
    int current_k_search_low = k_opt_low;
    int current_k_search_high = std::min(p_mid, k_opt_high);
    
    // Initialize best_k_for_pmid to a value in the current search range to ensure it's valid
    // even if dp_vals[p_mid] remains INF.
    if (current_k_search_low <= current_k_search_high) {
         best_k_for_pmid = current_k_search_low; // Default, can be any in range
    } else {
        // If search range is empty, dp_vals[p_mid] will remain INF.
        // Pass conservative k_opt ranges to children.
        // best_k_for_pmid = k_opt_low for left child, k_opt_high for right child.
        // This case is complex, better to ensure best_k_for_pmid is always set if loop runs.
        // If loop doesn't run current_k_search_low > current_k_search_high:
        // Left call: solve_dp(p_low, p_mid - 1, k_opt_low, k_opt_high);
        // Right call: solve_dp(p_mid + 1, p_high, k_opt_low, k_opt_high);
        // But the problem guarantees a solution, so this path for empty search range
        // should not be the sole path to finite solution.
        // The Knuth property should ensure k_opt_low <= k_opt_high.
        // A safe default for best_k_for_pmid if no k improves dp_vals[p_mid] from INF:
        best_k_for_pmid = k_opt_low; // Defaulting to k_opt_low
    }


    for (int k = current_k_search_low; k <= current_k_search_high; ++k) {
        // k is the starting garbage index for person p_mid.
        // It must be non-negative. This is ensured as k_opt_low starts at 0
        // and subsequent k_opt_low/high are from previous best_k (which are >=0).
        
        int128 prev_dp_val = (k == 0) ? 0 : dp_vals[k - 1];
        
        if (prev_dp_val == INF) { // If the previous state is unreachable, skip
            continue;
        }

        int128 cost_of_segment = calculate_cost_for_segment(p_mid, k);
        
        // Check for overflow before addition if prev_dp_val or cost_of_segment is huge
        // But INF + finite_cost is still INF.
        if (cost_of_segment == INF) continue; // Should not happen with problem constraints

        int128 current_total_cost = prev_dp_val + cost_of_segment;

        if (current_total_cost < dp_vals[p_mid]) {
            dp_vals[p_mid] = current_total_cost;
            best_k_for_pmid = k;
        }
    }

    // After finding optimal k for p_mid, recurse.
    // If dp_vals[p_mid] is INF, best_k_for_pmid might not be "optimal" but a valid index.
    // If no k was found (current_k_search_low > current_k_search_high), dp_vals[p_mid] stays INF.
    // best_k_for_pmid should be set to k_opt_low for left child, and k_opt_high for right child's opt_k range.
    // The logic: best_k_for_pmid is set to a valid k if dp_vals[p_mid] is updated.
    // If dp_vals[p_mid] remains INF, we can use k_opt_low for left call's upper bound on k,
    // and k_opt_high for right call's lower bound for k to pass on the widest possible valid range.
    // However, standard D&C opt relies on best_k_for_pmid being the actual argmin.
    // If dp[p_mid] is INF, any k in its search range is "optimal" for INF.
    // The choice of best_k_for_pmid = k_opt_low (or current_k_search_low) before loop handles this.

    solve_dp(p_low, p_mid - 1, k_opt_low, best_k_for_pmid);
    solve_dp(p_mid + 1, p_high, best_k_for_pmid, k_opt_high);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> N_val;

    A_vals.resize(N_val);
    X_vals.resize(N_val);
    Y_vals.resize(N_val);
    dp_vals.assign(N_val, INF);

    for (int i = 0; i < N_val; ++i) std::cin >> A_vals[i];
    for (int i = 0; i < N_val; ++i) std::cin >> X_vals[i];
    for (int i = 0; i < N_val; ++i) std::cin >> Y_vals[i];

    if (N_val == 0) { // Edge case, though constraints say N >= 1
        std::cout << 0 << std::endl;
        return 0;
    }
    
    solve_dp(0, N_val - 1, 0, N_val - 1);

    std::cout << dp_vals[N_val - 1] << std::endl;

    return 0;
}