結果
| 問題 |
No.1211 円環はお断り
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,972 bytes |
| コンパイル時間 | 1,107 ms |
| コンパイル使用メモリ | 101,516 KB |
| 実行使用メモリ | 48,360 KB |
| 最終ジャッジ日時 | 2025-05-14 13:02:10 |
| 合計ジャッジ時間 | 41,572 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 32 TLE * 9 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm> // Include for std::max
using namespace std;
// Use long long for potentially large sums
typedef long long ll;
int N; // Number of beads
int K; // Number of segments (people)
vector<ll> A; // Bead values
// Using a tripled array allows handling the cyclic nature by using linear indices.
// A segment starting near the end of the original N beads can wrap around,
// represented continuously in the tripled array.
vector<ll> A_triple;
vector<ll> P_triple; // Prefix sums for the tripled array
// Jump[p][k] stores the starting index of the segment after 2^k segments,
// starting from index p. This is used for binary lifting.
vector<vector<int>> Jump;
// K <= 10^5, log2(10^5) is approx 16.6. Max power k needed is 16.
// MAX_LOG_K = 17 covers k=0..16. Using 18 is safer just in case.
const int MAX_LOG_K = 18;
// Check function: Determines if it's possible to partition the ring into K segments
// such that each segment's sum is at least X.
bool can(ll X) {
// If X is 0, it's trivially possible as long as we can partition (N>=K>=1 holds).
if (X == 0) return true;
// Calculate Next[p] for p in [0, 3N-1).
// Next[p] is the starting index of the segment that follows the segment starting at p.
// If segment starts at p and ends at q, Next[p] = q+1.
// All indices are 0-based.
vector<int> Next(3 * N);
int q = 0; // Use two pointers technique: q tracks the potential end index of the segment starting at p.
for (int p = 0; p < 3 * N; ++p) {
// Ensure the segment end index q is at least the start index p.
q = max(p, q);
// Find the minimum index q >= p such that the sum of beads A[p...q] >= X.
// Use prefix sums for efficient sum calculation: P_triple[q+1] - P_triple[p] >= X.
// Also, a segment cannot be longer than N beads (the whole ring). Thus, q must be < p + N.
while (q < p + N && P_triple[q + 1] - P_triple[p] < X) {
q++; // Extend the segment end index q
}
if (q >= p + N) {
// If q reaches p+N, it means even taking N consecutive beads starting from p (effectively the whole ring),
// the sum is less than X. This happens only if total_sum < X.
// In this case, it's impossible to form a segment with sum >= X starting at p.
// Mark this path as failed using an out-of-bounds index (>= 3N).
Next[p] = 3 * N;
} else {
// Found a valid segment ending at q. The next segment must start at index q+1.
Next[p] = q + 1;
}
}
// Initialize the Jump table base case (k=0: jump of 2^0=1 step/segment)
// Jump[p][0] stores the index after 1 segment starting from p.
for (int p = 0; p < 3 * N; ++p) {
Jump[p][0] = Next[p];
}
// Fill the rest of the Jump table using dynamic programming (binary lifting)
// Jump[p][k] = starting index after 2^k segments, starting from p.
// Computed by combining two jumps of 2^(k-1) steps.
for (int k = 1; k < MAX_LOG_K; ++k) {
for (int p = 0; p < 3 * N; ++p) {
// intermediate = position after 2^(k-1) steps starting from p
int intermediate = Jump[p][k-1];
// Check if the intermediate index is already out of bounds (>= 3N).
// This signifies a failed path earlier.
if (intermediate >= 3 * N) {
Jump[p][k] = 3 * N; // Propagate the out-of-bounds state
} else {
// Compute the jump of 2^k steps by chaining two 2^(k-1) jumps:
// p -> intermediate -> Jump[intermediate][k-1]
Jump[p][k] = Jump[intermediate][k-1];
}
}
}
// Check each possible starting bead index p from 0 to N-1
for (int p = 0; p < N; ++p) {
int current_p = p; // The starting index for this sequence of segments
int k_steps = K; // Total number of segments (steps) needed
// Use binary lifting to find the final position after K segments
for(int k = MAX_LOG_K - 1; k >= 0; --k) {
// Check if the k-th bit of K is set (i.e., if 2^k contributes to K)
if ((k_steps >> k) & 1) {
// Before accessing Jump table, ensure current position is valid
if (current_p >= 3 * N) {
// If current position is already out of bounds, this path has failed. Stop processing.
break;
}
// Make a jump of 2^k segments
current_p = Jump[current_p][k];
}
}
// After K steps, current_p is the starting index of the (K+1)-th segment.
// The K segments covered beads from the original index p up to current_p - 1.
// The total number of beads covered is current_p - p.
// A valid partition exists if this total span is at most N beads.
// This condition ensures the K segments fit within one traversal of the ring without "overlapping" in terms of total length.
if (current_p - p <= N) {
return true; // Found a valid partition starting at p. X is achievable.
}
}
// If no starting position p from 0..N-1 leads to a valid partition, X is not achievable.
return false;
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input N and K
cin >> N >> K;
A.resize(N); // Resize vector A to hold N bead values
ll total_sum = 0; // Calculate total sum of bead values
bool non_zero_exists = false; // Flag to check if any bead has positive value
for (int i = 0; i < N; ++i) {
cin >> A[i];
total_sum += A[i];
if (A[i] > 0) non_zero_exists = true;
}
// Edge case: If all bead values are 0, the only possible minimum sum M is 0.
if (!non_zero_exists) {
cout << 0 << endl;
return 0;
}
// Create tripled array A_triple. This simplifies handling the ring structure.
// Indices [0, N-1] hold the original array.
// Indices [N, 2N-1] hold a copy.
// Indices [2N, 3N-1] hold another copy.
A_triple.resize(3 * N);
for (int i = 0; i < 3 * N; ++i) {
A_triple[i] = A[i % N];
}
// Compute prefix sums for the tripled array. P_triple[k] = sum of A_triple[0...k-1].
// Size 3N+1 needed for P_triple[q+1] - P_triple[p] calculation where q can be up to 3N-1.
P_triple.resize(3 * N + 1, 0);
for (int i = 0; i < 3 * N; ++i) {
P_triple[i + 1] = P_triple[i] + A_triple[i];
}
// Allocate memory for the Jump table. Size 3N is needed because intermediate indices can reach up to 3N.
// Rows correspond to starting indices p (0 to 3N-1). Columns correspond to jump power k (0 to MAX_LOG_K-1).
Jump.assign(3 * N, vector<int>(MAX_LOG_K));
// Binary search for the maximum possible minimum segment sum M (denoted as 'ans').
// The search range is [0, total_sum]. The upper bound is total_sum + 1 for the binary search logic.
ll low = 0, high = total_sum + 1, ans = 0;
while (low < high) {
// Calculate midpoint carefully to avoid potential overflow if low/high are large.
ll mid = low + (high - low) / 2;
if (can(mid)) {
// If a minimum sum of 'mid' is possible, 'mid' is a potential answer.
// We try to find a larger possible minimum sum, so update lower bound.
ans = mid;
low = mid + 1;
} else {
// If 'mid' is not possible, the maximum possible minimum sum must be smaller.
// Update upper bound.
high = mid;
}
}
// Output the final answer, which is the largest 'mid' for which can(mid) returned true.
cout << ans << endl;
return 0;
}