結果
| 問題 |
No.703 ゴミ拾い Easy
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 93 ms / 1,500 ms |
| コード長 | 9,580 bytes |
| コンパイル時間 | 1,660 ms |
| コンパイル使用メモリ | 87,712 KB |
| 実行使用メモリ | 12,672 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:40 |
| 合計ジャッジ時間 | 6,240 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 46 |
ソースコード
#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <algorithm> // For std::reverse
// Use __int128_t for intermediate calculations in CHT check to avoid overflow.
// This type is typically available in GCC and Clang.
#ifdef __GNUC__
using int128 = __int128_t;
#else
// Fallback for compilers that don't support __int128_t. This is risky and might lead to overflow.
// On platforms like AtCoder, Codeforces, this should generally work.
using int128 = long long;
// #warning "__int128_t not supported, using long long which might overflow." // You might want to uncomment this warning locally
#endif
// Function to print __int128_t (useful for local debugging, not typically needed for online judge submissions)
#ifdef __GNUC__
std::ostream& operator<<(std::ostream& os, int128 val) {
if (val == 0) return os << "0";
bool negative = false;
if (val < 0) {
negative = true;
val = -val; // Make positive
}
std::string s;
while (val > 0) {
s += (char)('0' + val % 10);
val /= 10;
}
if (negative) os << "-";
// Reverse the string to get the correct order of digits
std::reverse(s.begin(), s.end());
// Handle case where original value was 0, and after making positive it is still 0.
if (s.empty() && !negative) return os << "0";
return os << s;
}
#endif
// State variables
long long N; // Number of trash items and volunteers
std::vector<long long> a; // x-coordinates of volunteers
std::vector<long long> x; // x-coordinates of trash items
std::vector<long long> y; // y-coordinates of trash items
std::vector<long long> dp; // DP table: dp[i] stores minimum cost to collect trash 0..i-1
// Structure representing a line y = mx + c in the CHT
struct Line {
long long m; // slope (-2 * x_j)
long long c; // y-intercept (dp[j] + x_j^2 + y_j^2)
};
// Function to evaluate a line at a given x-coordinate (query_a)
// Uses 128-bit intermediate type to prevent overflow during multiplication.
long long eval(const Line& line, long long query_a) {
int128 val = (int128)line.m * query_a + line.c;
// Final result is expected to fit within long long based on problem constraints analysis.
return (long long)val;
}
// Convexity check function for CHT.
// Determines if adding line `r` after line `q` maintains the lower envelope property,
// given that line `p` comes before `q`.
// Returns true if `q` should be kept (convexity holds), false if `q` is redundant and should be removed.
bool check(const Line& p, const Line& q, const Line& r) {
// The condition for convexity (q being useful) is that the intersection point of (p, q)
// is less than or equal to the intersection point of (q, r).
// Intersection point x* = (c2 - c1) / (m1 - m2)
// We want x*_pq <= x*_qr => (q.c - p.c) / (p.m - q.m) <= (r.c - q.c) / (q.m - r.m)
// Assuming slopes are strictly decreasing (p.m > q.m > r.m), both denominators are positive.
// Cross-multiplying gives: (q.c - p.c) * (q.m - r.m) <= (r.c - q.c) * (p.m - q.m)
// This form avoids floating point numbers and uses 128-bit integers to prevent overflow.
int128 cq_minus_cp = (int128)q.c - p.c;
int128 mq_minus_mr = (int128)q.m - r.m;
int128 cr_minus_cq = (int128)r.c - q.c;
int128 mp_minus_mq = (int128)p.m - q.m;
// Perform the check using 128-bit integers
int128 val1 = cq_minus_cp * mq_minus_mr;
int128 val2 = cr_minus_cq * mp_minus_mq;
// The inequality val1 <= val2 determines if q should be kept.
// This check is robust even if some slopes are equal due to properties of inequalities,
// as long as the insertion logic correctly handles dominated lines with equal slopes first.
return val1 <= val2;
}
int main() {
// Optimize standard IO operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read input size
std::cin >> N;
// Handle the edge case N=0
if (N == 0) {
std::cout << 0 << std::endl;
return 0;
}
// Resize vectors and read input data
a.resize(N);
x.resize(N);
y.resize(N);
for (int i = 0; i < N; ++i) std::cin >> a[i];
for (int i = 0; i < N; ++i) std::cin >> x[i];
for (int i = 0; i < N; ++i) std::cin >> y[i];
// Initialize DP table. dp[i] stores minimum cost for trash 0...i-1.
dp.resize(N + 1);
dp[0] = 0; // Base case: cost is 0 for collecting 0 trash items.
// Deque to maintain the lower envelope of lines for CHT
std::deque<Line> hull;
// Add the first line L_0 corresponding to the base case (j=0)
long long x0 = x[0];
long long y0 = y[0];
Line l0;
l0.m = -2 * x0;
// Explicitly cast squares to long long to avoid potential intermediate overflow if x0, y0 were large ints.
l0.c = dp[0] + (long long)x0 * x0 + (long long)y0 * y0;
hull.push_back(l0);
// Iterate through the DP states from i=1 to N
for (int i = 1; i <= N; ++i) {
// The current query point is the x-coordinate of person i-1
long long current_a = a[i - 1];
// Query Step: Find the line in the hull that gives the minimum value at current_a.
// Since query points 'a' are non-decreasing and slopes 'm' are non-increasing,
// we can efficiently find the minimum by removing lines from the front of the deque.
while (hull.size() >= 2) {
// Get the first two lines from the deque
Line l1 = hull[0];
Line l2 = hull[1];
// If slopes are equal, remove the one with larger intercept (less optimal).
if (l1.m == l2.m) {
if (l1.c >= l2.c) { // L1 is above or same as L2
hull.pop_front(); // Remove L1
} else { // L1 is below L2
// L1 is better. L2 is suboptimal but might be needed later. Keep both for now.
// But L1 will be the minimum found. Stop removing from front.
break;
}
} else { // Slopes are different. Since CHT maintains decreasing slopes, l1.m > l2.m.
// Check if L1 is worse than or equal to L2 at current_a.
// Use the condition: current_a >= intersection_x point of L1 and L2
// Equivalent cross-multiplication form: current_a * (m1 - m2) >= c2 - c1
int128 lhs = (int128)(l1.m - l2.m) * current_a;
int128 rhs = (int128)l2.c - l1.c;
if (lhs >= rhs) { // L1 is worse or equal than L2 at current_a
hull.pop_front(); // Remove L1 as it's no longer optimal
} else { // L1 is strictly better than L2 at current_a
break; // L1 is the optimal line for this query point
}
}
}
// The line at the front of the deque is now the optimal one for current_a
long long min_val = eval(hull.front(), current_a);
// Calculate dp[i] using the found minimum value. Use 128-bit intermediate for safety.
dp[i] = (long long)((int128)current_a * current_a + min_val);
// Add Step: Add a new line corresponding to the state dp[i] for future computations.
// This line will be based on trash item i. This happens only if i < N.
if (i < N) {
long long xi = x[i];
long long yi = y[i];
Line new_line;
new_line.m = -2 * xi;
// Calculate intercept c = dp[i] + x_i^2 + y_i^2. Use long long casts for squares.
new_line.c = dp[i] + (long long)xi * xi + (long long)yi * yi;
bool add_this_line = true; // Flag to track if the new line should be added
// Before adding, handle lines with the same slope as the new line.
// Remove lines from the back if they have the same slope and are dominated (>= intercept).
while (!hull.empty() && hull.back().m == new_line.m) {
if (hull.back().c >= new_line.c) { // Existing line at back is worse or equal
hull.pop_back(); // Remove it
} else { // Existing line at back is better (smaller intercept)
add_this_line = false; // New line is dominated, don't add it
break; // Stop checking and skip adding
}
}
// Only proceed if the new line is not dominated by an existing line with same slope
if(add_this_line) {
// Maintain convexity: Remove lines from the back that become redundant after adding the new line.
while (hull.size() >= 2) {
Line p = hull[hull.size() - 2]; // Second to last line
Line q = hull.back(); // Last line
// Call the check function to see if q remains useful with new_line (r)
if (!check(p, q, new_line)) { // If check returns false, q is redundant
hull.pop_back(); // Remove q
} else { // Convexity holds with q
break; // Stop removing
}
}
// Add the new line to the back of the deque
hull.push_back(new_line);
}
// If add_this_line was false, we skip adding the line.
}
}
// The final answer is the minimum cost to collect all N trash items (0..N-1).
std::cout << dp[N] << std::endl;
return 0;
}