結果
| 問題 |
No.2330 Eat Slime
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,515 ms / 4,000 ms |
| コード長 | 10,310 bytes |
| コンパイル時間 | 2,683 ms |
| コンパイル使用メモリ | 111,312 KB |
| 実行使用メモリ | 63,556 KB |
| 最終ジャッジ日時 | 2025-05-14 13:02:20 |
| 合計ジャッジ時間 | 35,539 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <vector> // Ensure vector is included
// Use long double for potentially better precision in FFT calculations
using namespace std;
typedef long long ll;
// Check compiler support for long double complex types and math functions
#if defined(__GNUC__) || defined(__clang__)
// Use long double on GCC/Clang environments where it typically offers higher precision
typedef complex<long double> cld;
const long double PI_LD = acosl(-1.0L);
// Macros for math functions to use long double versions
#define ROUND_FUNC roundl
#define COS_FUNC cosl
#define SIN_FUNC sinl
#else
// Fallback to standard double if long double specifics are unknown or it offers no advantage
typedef complex<double> cld;
const double PI_LD = acos(-1.0);
#define ROUND_FUNC round
#define COS_FUNC cos
#define SIN_FUNC sin
#endif
/**
* @brief Iterative Fast Fourier Transform implementation.
*
* @param a The vector of complex numbers to transform. It is modified in-place.
* @param invert If true, performs inverse FFT. Otherwise, performs forward FFT.
*
* This implementation uses the Cooley-Tukey algorithm with bit-reversal permutation.
* It is adapted from standard competitive programming resources.
*/
void fft_iterative(vector<cld>& a, bool invert) {
int n = a.size();
if (n == 1) return; // Base case: FFT of size 1 is identity
// Bit-reversal permutation: reorders elements according to bit-reversed indices
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
// Find the next index j by reversing the bits of i
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j) // Swap elements if i < j to avoid double swaps
swap(a[i], a[j]);
}
// Cooley-Tukey algorithm: iteratively combine smaller FFT results
for (int len = 2; len <= n; len <<= 1) {
// Angle for the current stage's roots of unity
long double ang = 2 * PI_LD / len * (invert ? -1 : 1);
cld wlen(COS_FUNC(ang), SIN_FUNC(ang)); // Principal len-th root of unity
for (int i = 0; i < n; i += len) { // Iterate through blocks of size len
cld w(1); // Start with w = 1 (the 0-th power root of unity)
for (int j = 0; j < len / 2; j++) { // Combine pairs of elements
cld u = a[i + j]; // Element from first half
cld v = a[i + j + len / 2] * w; // Element from second half multiplied by root of unity
a[i + j] = u + v; // Butterfly operation: sum
a[i + j + len / 2] = u - v; // Butterfly operation: difference
w *= wlen; // Move to the next root of unity
}
}
}
// If performing inverse FFT, scale the results by 1/n
if (invert) {
for (cld& x : a) {
x /= n;
}
}
}
/**
* @brief Multiplies two polynomials represented by vectors of coefficients using FFT.
*
* @param a Coefficients of the first polynomial. a[i] is coefficient of z^i.
* @param b Coefficients of the second polynomial. b[i] is coefficient of z^i.
* @return Vector of coefficients of the product polynomial.
*
* Handles potential zero polynomials. Uses FFT for efficiency. Rounds results to nearest long long.
*/
vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
// Check for zero polynomial inputs to optimize or handle edge cases
bool a_is_zero = all_of(a.begin(), a.end(), [](ll v){ return v == 0; });
bool b_is_zero = all_of(b.begin(), b.end(), [](ll v){ return v == 0; });
// If either polynomial is zero, the product is the zero polynomial. Return [0].
if (a_is_zero || b_is_zero) {
return vector<ll>{0};
}
// Convert coefficient vectors to complex vectors for FFT
vector<cld> fa(a.size()), fb(b.size());
for(size_t i=0; i<a.size(); ++i) fa[i] = a[i];
for(size_t i=0; i<b.size(); ++i) fb[i] = b[i];
// Determine required FFT size: smallest power of 2 >= degree of product + 1
int n = 1;
// Degree of product = (a.size()-1) + (b.size()-1). Size needed = degree + 1 = a.size()+b.size()-1
while (n < a.size() + b.size() - 1) n <<= 1;
// Resize vectors to FFT size, padding with zeros
fa.resize(n);
fb.resize(n);
// Perform forward FFT on both polynomials
fft_iterative(fa, false);
fft_iterative(fb, false);
// Pointwise multiplication in frequency domain
for (int i = 0; i < n; i++)
fa[i] *= fb[i];
// Perform inverse FFT to get coefficients of the product polynomial
fft_iterative(fa, true);
// Maximum possible degree of the product polynomial
// If a has degree deg_a = a.size()-1, b has deg_b = b.size()-1, product has degree deg_a + deg_b.
// Minimum degree is 0 if both input polynomials have degree 0.
int res_max_deg = (a.size() > 0 ? a.size() - 1 : 0) + (b.size() > 0 ? b.size() - 1 : 0);
int res_size = res_max_deg + 1; // Size of result vector based on max possible degree
vector<ll> result(res_size);
// Extract real parts and round to nearest long long for coefficients
for (int i = 0; i < res_size; i++) {
// Check index validity against FFT result size `n`
if (i < fa.size()) {
// Round the real part to get the integer coefficient
result[i] = ROUND_FUNC(fa[i].real());
} else {
// Coefficients beyond n are effectively zero
result[i] = 0;
}
}
// Optional: Trim trailing zeros from the result vector
// This makes the vector represent the exact degree of the polynomial
int true_size = result.size();
while (true_size > 1 && result[true_size - 1] == 0) {
true_size--;
}
result.resize(true_size);
// Ensure the result vector is never empty unless it represents the zero polynomial ([0])
if (result.empty()) return vector<ll>{0};
return result;
}
int main() {
// Optimize input/output operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of slimes
int M; // Number of bonus conditions
ll X; // Score per eaten slime
cin >> N >> M >> X;
// Handle the edge case N=0 immediately
if (N == 0) {
cout << 0 << endl;
return 0;
}
// Read slime colors (1-based indexing in problem, stored 0-based in vector C)
vector<int> C(N);
for (int i = 0; i < N; ++i) {
cin >> C[i];
}
// Precompute P_c polynomials for each color c. P_coeffs[c][a] = total bonus Y_j for color c at position a.
vector<vector<ll>> P_coeffs(6, vector<ll>(N + 1, 0)); // Size N+1 for degrees 0 to N. Index 0 unused for positions.
for (int j = 0; j < M; ++j) {
int A; // Required position (1-based)
int B; // Required color (1 to 5)
ll Y; // Bonus score
cin >> A >> B >> Y;
// Validate input bounds before using them as indices
if (A >= 1 && A <= N && B >= 1 && B <= 5) {
P_coeffs[B][A] += Y; // Add bonus Y to coefficient for z^A for color B
}
}
// Initialize total scores for eating k slimes (k=0 to N). Initial score is k*X.
vector<ll> total_score(N + 1);
for (int k = 0; k <= N; ++k) {
total_score[k] = (ll)k * X;
}
// For each color c from 1 to 5
for (int c = 1; c <= 5; ++c) {
// Copy P_coeffs for current color c to avoid modification if needed elsewhere
vector<ll> current_P_coeffs = P_coeffs[c];
// Construct T_c polynomial based on slime positions with color c.
// T_coeffs[p] = 1 if there is a slime of color c at original position i such that p = N-i.
vector<ll> current_T_coeffs(N + 1, 0); // Size N+1 for degrees 0 to N.
bool color_exists = false; // Flag to check if any slime has color c
for (int i = 0; i < N; ++i) { // Iterate through 0-based indices
if (C[i] == c) {
// Slime at original position i+1 has color c
// Set coefficient for z^{N-(i+1)} to 1. Index is N-(i+1).
current_T_coeffs[N - (i + 1)] = 1;
color_exists = true;
}
}
// Check if P or T polynomials are effectively zero before FFT multiplication
bool P_is_zero = all_of(current_P_coeffs.begin(), current_P_coeffs.end(), [](ll v){ return v == 0; });
// If no slime of color c exists, T_c is zero. If no bonuses target color c, P_c is zero.
// If either is zero, their product is zero, so skip FFT.
if (!color_exists || P_is_zero) {
continue;
}
// Compute the product polynomial Q_c = P_c * T_c using FFT
vector<ll> Q_c = multiply(current_P_coeffs, current_T_coeffs);
// Add the contribution of Q_c coefficients to the total score
// The coefficient Q_c[N-k] corresponds to the bonus points obtained when eating k slimes for color c.
for (int k = 0; k <= N; ++k) {
int exponent = N - k; // Exponent relevant for k eaten slimes
// Check if the exponent is a valid index in the result polynomial Q_c
if (exponent >= 0 && exponent < Q_c.size()) {
total_score[k] += Q_c[exponent]; // Add bonus points to score for eating k slimes
}
}
}
// Find the maximum score among all possible numbers of eaten slimes (k=0 to N)
ll max_score = 0;
if (!total_score.empty()) { // Should not be empty due to N=0 check earlier
max_score = total_score[0]; // Initialize max score with the score for k=0
// Iterate from k=1 to N to find the overall maximum score
for (int k = 1; k <= N; ++k) {
// Check index validity (though total_score has size N+1)
if (k < total_score.size()) {
max_score = max(max_score, total_score[k]);
}
}
// Ensure the final maximum score is non-negative (as per problem constraints X>=0, Y>=1)
max_score = max(0LL, max_score);
}
// Output the maximum possible score
cout << max_score << endl;
return 0;
}