結果
| 問題 |
No.919 You Are A Project Manager
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 41 ms / 3,000 ms |
| コード長 | 10,422 bytes |
| コンパイル時間 | 1,593 ms |
| コンパイル使用メモリ | 115,220 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:15:51 |
| 合計ジャッジ時間 | 4,256 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 55 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath> // For std::log2
// Define a structure for the nodes of the persistent segment tree
struct Node {
long long count; // Stores the number of elements in the range represented by this node
int left, right; // Indices of the left and right children in the 'tree' vector (node pool)
Node() : count(0), left(0), right(0) {} // Default constructor
};
// Global vector to store all nodes of the segment trees (node pool)
std::vector<Node> tree;
// Global vector to store the root indices of different versions of the segment tree
// roots[i] stores the root for the prefix A[0...i-1]
std::vector<int> roots;
// Global index for allocating new nodes from the pool
int node_pool_idx = 1; // Start idx from 1, index 0 represents a null node
/**
* @brief Updates the persistent segment tree by adding an element.
*
* Creates a new version of the tree based on a previous version 'prev_root'
* by incrementing the count for the element at position 'pos' (in the compressed value range).
* The segment tree operates on the value range [L, R].
*
* @param prev_root Index of the root node of the previous version.
* @param L The lower bound of the current node's value range.
* @param R The upper bound of the current node's value range.
* @param pos The compressed rank (position) of the value being added.
* @return Index of the root node of the new version.
*/
int update(int prev_root, int L, int R, int pos) {
int new_root = node_pool_idx++; // Allocate a new node index
// Dynamic resizing of the node pool vector if it runs out of space
if (new_root >= tree.size()) {
// Increase size; using 1.5x growth factor is common for amortized efficiency
tree.resize(tree.size() * 1.5 + 1);
}
// Copy data from the corresponding node in the previous version
tree[new_root] = tree[prev_root];
tree[new_root].count++; // Increment the count because we added an element in this path
// If this is a leaf node (range contains single value), return the new node index
if (L == R) {
return new_root;
}
int mid = L + (R - L) / 2; // Calculate midpoint, avoiding potential overflow
// Recursively update the appropriate child (left or right) based on 'pos'
if (pos <= mid) { // If the position is in the left half of the range
tree[new_root].left = update(tree[prev_root].left, L, mid, pos);
} else { // If the position is in the right half
tree[new_root].right = update(tree[prev_root].right, mid + 1, R, pos);
}
return new_root; // Return index of the newly created root node for this version
}
/**
* @brief Queries the persistent segment tree to find the rank of the k-th smallest element.
*
* Finds the rank (index in the compressed value range) of the k-th smallest element
* within the subarray represented by the difference between tree versions 'r2' and 'r1'.
* The segment tree operates on the value range [L, R].
*
* @param r1 Index of the root node for the version representing the prefix *before* the query range.
* @param r2 Index of the root node for the version representing the prefix *at the end* of the query range.
* @param L The lower bound of the current node's value range.
* @param R The upper bound of the current node's value range.
* @param k The rank of the element to find (e.g., k=1 for minimum, k=N/2 for median-like).
* @return The compressed rank (index) of the k-th smallest element.
*/
int query(int r1, int r2, int L, int R, int k) {
// Base case: If we reach a leaf node, its range [L,R] has L=R. This L is the rank.
if (L == R) {
return L;
}
// Calculate the count of elements in the left subtree within the specified range.
// This is the difference between counts in version r2 and version r1.
long long left_count = tree[tree[r2].left].count - tree[tree[r1].left].count;
int mid = L + (R - L) / 2; // Calculate midpoint
// Decide whether to search in the left or right subtree
if (k <= left_count) { // If the k-th element is within the left subtree's count
return query(tree[r1].left, tree[r2].left, L, mid, k);
} else { // If the k-th element is within the right subtree's count
// Adjust k for the search in the right subtree: we are now looking for the (k - left_count)-th element in the right part.
return query(tree[r1].right, tree[r2].right, mid + 1, R, k - left_count);
}
}
int main() {
// Use faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of programmers
std::cin >> N;
std::vector<long long> A(N); // Stores motivation values
std::vector<long long> unique_vals_vec; // Used for coordinate compression
unique_vals_vec.reserve(N); // Reserve capacity to potentially avoid reallocations
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
unique_vals_vec.push_back(A[i]);
}
// Coordinate Compression: Map large motivation values to smaller integer ranks [0, D-1]
std::sort(unique_vals_vec.begin(), unique_vals_vec.end());
// Remove duplicate values
unique_vals_vec.erase(std::unique(unique_vals_vec.begin(), unique_vals_vec.end()), unique_vals_vec.end());
std::map<long long, int> val_to_rank; // Map original value to its rank
std::vector<long long> rank_to_val(unique_vals_vec.size()); // Map rank back to original value
for (int i = 0; i < unique_vals_vec.size(); ++i) {
val_to_rank[unique_vals_vec[i]] = i;
rank_to_val[i] = i; // Store original value at index corresponding to its rank
}
// Corrected map: rank_to_val should store original value
for (int i = 0; i < unique_vals_vec.size(); ++i) {
rank_to_val[i] = unique_vals_vec[i];
}
int D = unique_vals_vec.size(); // Number of distinct motivation values
// Estimate initial size for the segment tree node pool. N * logN nodes approximately.
// Add a buffer factor for safety.
int initial_tree_size = std::max((int)(N * (std::log2(N+1) + 4)), 100); // Increased buffer
tree.resize(initial_tree_size);
roots.resize(N + 1); // Need N+1 roots for prefixes of length 0 to N
tree[0] = Node(); // Initialize the null node (node 0)
roots[0] = 0; // roots[0] corresponds to the empty prefix
// Build the persistent segment tree versions for all prefixes A[0...i]
for (int i = 0; i < N; ++i) {
// roots[i+1] is built upon roots[i] by adding element A[i]
roots[i+1] = update(roots[i], 0, D - 1, val_to_rank[A[i]]);
}
long long max_total_productivity = 0; // Stores the overall maximum productivity found
// Iterate through all possible team sizes K from 1 to N
for (int K = 1; K <= N; ++K) {
int M = N / K; // Maximum number of teams that can be formed consecutively from one end
if (M == 0) continue; // If N < K, we cannot form any team of size K
// L[p] stores the total productivity of the first p teams taken from the left
std::vector<long long> L(M + 1, 0);
// R[q] stores the total productivity of the first q teams taken from the right
std::vector<long long> R(M + 1, 0);
// Determine the rank 'k_th' needed for the median calculation based on K
// Problem statement definition: B[K/2] if K even, B[(K+1)/2] if K odd.
// This corresponds to the k-th smallest element where k = K/2 for even K, (K+1)/2 for odd K.
int k_th = (K % 2 == 1) ? (K + 1) / 2 : K / 2;
// Precompute L[p] values: Sum of productivities for teams taken from the left
for (int p = 1; p <= M; ++p) {
int start_idx = (p - 1) * K; // 0-based start index of the p-th block from left
int end_idx = p * K - 1; // 0-based end index of the p-th block from left
// Query the k-th element's rank in the range [start_idx, end_idx]
// Using roots[start_idx] (version before range) and roots[end_idx + 1] (version at end of range)
int rank = query(roots[start_idx], roots[end_idx + 1], 0, D - 1, k_th);
long long median_val = rank_to_val[rank]; // Map rank back to original value
// Add productivity of this team to the previous sum
L[p] = L[p-1] + (long long)K * median_val;
}
// Precompute R[q] values: Sum of productivities for teams taken from the right
for (int q = 1; q <= M; ++q) {
int start_idx = N - q * K; // 0-based start index of the q-th block from right
int end_idx = N - (q - 1) * K - 1; // 0-based end index of the q-th block from right
// Query the k-th element's rank in this range
int rank = query(roots[start_idx], roots[end_idx + 1], 0, D - 1, k_th);
long long median_val = rank_to_val[rank]; // Map rank back to original value
// Add productivity of this team to the previous sum
R[q] = R[q-1] + (long long)K * median_val;
}
// Compute MaxR[k] = max_{0 <= i <= k} R[i] using prefix maximums
std::vector<long long> MaxR(M + 1);
MaxR[0] = R[0]; // Base case: MaxR[0] = R[0] = 0
for (int q = 1; q <= M; ++q) {
// MaxR[q] is the maximum value found in R[0]...R[q]
MaxR[q] = std::max(MaxR[q-1], R[q]);
}
// Find the maximum possible total productivity for the current K
// Using the O(M) approach: max_{0 <= p <= M} (L[p] + MaxR[M-p])
long long current_K_max_prod = 0; // Max productivity for this K, initialized to 0 (option of forming no teams)
for (int p = 0; p <= M; ++p) {
int max_q_idx = M - p; // The maximum index for q such that p + q <= M
if (max_q_idx >= 0) { // Check if the index for MaxR is valid
// Calculate potential total productivity and update maximum for this K
current_K_max_prod = std::max(current_K_max_prod, L[p] + MaxR[max_q_idx]);
}
}
// Update the overall maximum productivity found across all K values
max_total_productivity = std::max(max_total_productivity, current_K_max_prod);
}
// Print the final result
std::cout << max_total_productivity << std::endl;
return 0;
}