結果
| 問題 |
No.1297 銅像
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:12:44 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,173 bytes |
| コンパイル時間 | 842 ms |
| コンパイル使用メモリ | 95,764 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:45 |
| 合計ジャッジ時間 | 5,698 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 TLE * 1 -- * 13 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath> // Required for abs function
using namespace std;
// Use long long for costs as they can potentially exceed the range of a 32-bit integer.
// The problem statement specifies costs up to 10^12, and total cost can accumulate.
typedef long long ll;
// Define a sufficiently large value to represent infinity.
// The maximum possible total cost can be estimated. Suppose one craftsman builds all statues.
// Max cost could be roughly N * (max(a_i) + max_transport + max(b_i))
// Max transport cost is roughly N * C <= 10^5 * 10^6 = 10^11.
// Max cost ~ 10^5 * (10^12 + 10^11 + 10^12) ~ 10^5 * (2.1 * 10^12) ~ 2.1 * 10^17.
// This value fits within a 64-bit signed long long (max value ~9e18).
// We use 4e18 as a safe upper bound constant for INF, significantly larger than max possible cost.
const ll INF = 4e18;
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of islands and craftsmen
ll C; // Cost factor for transportation
cin >> N >> C;
// Store work fees (a_i) and design fees (b_i) for each craftsman i.
// Using 0-based indexing for vectors a and b.
vector<ll> a(N), b(N);
for (int i = 0; i < N; ++i) {
cin >> a[i] >> b[i];
}
// Dynamic Programming approach based on the observation that there exists an optimal solution
// where the assignments are monotone: if craftsman i_j builds the statue on island j,
// then i_j <= i_{j+1} for all j=1..N-1.
// Let DP[j][k] be the minimum cost to build statues on islands 1 to j,
// such that island j is assigned to craftsman k. The assignments for 1..j satisfy monotonicity.
//
// We can optimize space complexity by only keeping track of the DP values for the previous island (j-1)
// to compute the values for the current island (j).
// Use 1-based indexing for islands (j) and craftsmen (k) in DP states for clarity, matching the problem statement.
// current_dp[k] will store DP[j][k] during computation for island j
vector<ll> current_dp(N + 1, INF);
// prev_dp[k] stores DP[j-1][k] from the previous island j-1
vector<ll> prev_dp(N + 1, INF);
// M_prev[k] will store the prefix minimum: min_{p=1..k} prev_dp[p]
// This helps compute the transition efficiently.
vector<ll> M_prev(N + 1, INF);
// Base case: j=1 (first island)
// Calculate the cost if island 1 is assigned to craftsman k (k=1..N)
for (int k = 1; k <= N; ++k) {
// Transportation cost for craftsman k (at location k) to build on island 1 (at location 1)
// Explicitly cast indices to ll to avoid potential intermediate overflow issues if N is large.
ll transport_cost = abs((ll)k - 1LL) * C;
// Total cost = work fee a_k + transport cost + design fee b_k
// The design fee b_k is always paid because this is the first time craftsman k is used in this path.
// Access arrays a and b using 0-based index k-1.
// Check for potential overflow before each addition.
ll current_cost = a[k - 1];
// Check if adding transport_cost overflows
if (transport_cost > INF - current_cost) {
prev_dp[k] = INF; // Set to INF if overflow would occur
} else {
current_cost += transport_cost;
// Check if adding design_fee b[k-1] overflows
if (b[k - 1] > INF - current_cost) {
prev_dp[k] = INF; // Set to INF if overflow would occur
} else {
prev_dp[k] = current_cost + b[k - 1];
}
}
}
// Compute DP table row by row, iterating through islands j from 2 to N
for (int j = 2; j <= N; ++j) {
// Compute prefix minima M_prev based on the DP values from the previous row (prev_dp corresponds to DP[j-1])
M_prev[0] = INF; // Initialize base case for prefix minimum calculation
for(int k = 1; k <= N; ++k) {
M_prev[k] = min(M_prev[k-1], prev_dp[k]);
}
// Calculate current row DP values (current_dp corresponds to DP[j])
fill(current_dp.begin(), current_dp.end(), INF); // Initialize current row DP values with INF
// Iterate through all possible craftsmen k for island j
for (int k = 1; k <= N; ++k) {
// Calculate the cost incurred specifically for assigning island j to craftsman k.
// This includes the work fee a_k and transportation cost |k-j|*C.
ll variable_cost = a[k - 1]; // Work fee
ll transport_cost = abs((ll)k - (ll)j) * C; // Transportation cost
// Check for overflow when calculating variable_cost
if (transport_cost > INF - variable_cost) {
variable_cost = INF; // Use INF if overflow occurs
} else {
variable_cost += transport_cost;
}
// If variable cost itself is INF (due to overflow or large base values), skip update for this k.
if (variable_cost == INF) {
continue;
}
// The recurrence relation for DP[j][k] is:
// DP[j][k] = (a_k + C|k-j|) + min( DP[j-1][k], b_k + min_{p=1..k-1} DP[j-1][p] )
// This considers two possibilities for the state reaching (j, k):
// Option 1: The craftsman for island j-1 was also k.
// The cost is DP[j-1][k] + variable_cost_for_j.
// Design fee b_k is already included in DP[j-1][k] if k was used.
ll cost1 = INF;
if (prev_dp[k] != INF) { // Check if the previous state is reachable
// Check for potential overflow before adding variable_cost
if (variable_cost > INF - prev_dp[k]) {
// cost1 remains INF if overflow would occur
} else {
cost1 = variable_cost + prev_dp[k];
}
}
// Option 2: The craftsman for island j-1 was p, where p < k.
// The cost is min_{p=1..k-1} DP[j-1][p] + b_k + variable_cost_for_j.
// The term min_{p=1..k-1} DP[j-1][p] is efficiently retrieved using M_prev[k-1].
// The design fee b_k must be added because craftsman k is used for the first time
// in the sequence of craftsmen when transitioning from p < k to k.
ll cost2 = INF;
if (M_prev[k - 1] != INF) { // Check if any path ending with p < k is reachable
ll min_prev_cost_prefix = M_prev[k - 1];
ll design_fee = b[k - 1];
// Check for overflow when adding design fee b_k
if (min_prev_cost_prefix > INF - design_fee) {
// If min_prev_cost + design_fee overflows, this path cost is effectively INF
} else {
ll combined_prev_cost = min_prev_cost_prefix + design_fee;
// Check for potential overflow when adding variable_cost
if (variable_cost > INF - combined_prev_cost) {
// cost2 remains INF if overflow would occur
} else {
cost2 = variable_cost + combined_prev_cost;
}
}
}
// The DP value DP[j][k] is the minimum cost from either Option 1 or Option 2.
current_dp[k] = min(cost1, cost2);
}
// Update prev_dp for the next iteration (j+1). The computed 'current_dp' becomes the 'prev_dp'.
prev_dp = current_dp;
}
// The final minimum total cost is the minimum value in the last row of the DP table (j=N),
// minimized over all possible craftsmen k assigned to the last island N.
ll min_total_cost = INF;
// After the loop for j=N finishes, prev_dp holds the DP[N] values
for (int k = 1; k <= N; ++k) {
min_total_cost = min(min_total_cost, prev_dp[k]);
}
cout << min_total_cost << endl;
return 0;
}