結果
| 問題 | No.3513 Greedy Yokan Party |
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-04-24 23:07:51 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,171 bytes |
| 記録 | |
| コンパイル時間 | 3,015 ms |
| コンパイル使用メモリ | 338,152 KB |
| 実行使用メモリ | 7,976 KB |
| 最終ジャッジ日時 | 2026-04-24 23:08:06 |
| 合計ジャッジ時間 | 11,396 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge4_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 9 WA * 17 |
ソースコード
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_ALGORITHM_SEARCH_BINARYSEARCH_HPP
#define KWM_T_ALGORITHM_SEARCH_BINARYSEARCH_HPP
#include <cstdlib>
/**
* @brief 二分探索 (整数)
*
* @details
* 単調性を持つ述語 f(x) に対して、f(x)=true となる境界を探索する。
* 初期状態で ok は true、ng は false を満たしている必要がある。
*
* Typical Use:
* 最大/最小の条件を満たす整数を探す
*
* Complexity:
* Time: O(log |ok-ng|)
*
* Template Parameters:
* T : 整数型 (int / long long など)
* F : bool f(T) を返す関数オブジェクト
*
* Parameters:
* ok : 条件を満たす値
* ng : 条件を満たさない値
* f : 判定関数
*
* Return:
* 条件を満たす境界値
*
* Requirements:
* f(ok) == true
* f(ng) == false
*
* Notes:
* ok と ng の大小関係は問わない
*
* Example:
* ```cpp
* auto f = [&](long long x){
* return x * x <= 100;
* };
*
* long long ans = binarySearch(0LL, 11LL, f);
* ```
*
* Verified:
*
*/
namespace kwm_t::algorithm::search {
template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
while (std::abs(ok - ng) > 1) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
}
/**
* @brief 二分探索 (実数)
*
* @details
* 実数値に対する二分探索。
* 回数固定で探索を行う。
*
* Typical Use:
* 実数解の近似探索
*
* Complexity:
* Time: O(counter)
*
* Template Parameters:
* T : 浮動小数点型 (double / long double)
* F : bool f(T) を返す関数オブジェクト
*
* Parameters:
* ok : 条件を満たす値
* ng : 条件を満たさない値
* f : 判定関数
* counter : 反復回数
*
* Return:
* 条件を満たす近似値
*
* Requirements:
* f(ok) == true
* f(ng) == false
*
* Example:
* ```cpp
* auto f = [&](double x){
* return x * x <= 2.0;
* };
*
* double ans = binarySearchDouble(0.0, 2.0, f);
* ```
*
* Verified:
*
*/
namespace kwm_t::algorithm::search {
template <class T, class F>
T binarySearchDouble(T ok, T ng, const F &f, int counter = 100) {
while (counter--) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
} // namespace kwm_t::algorithm::search
#endif // KWM_T_ALGORITHM_SEARCH_BINARYSEARCH_HPP
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// second maxの最大化
// k-1がn-1個作れたら駄目？
int n, l; cin >> n >> l;
int k; cin >> k;
vector<int>a(n);
rep(i, n)cin >> a[i];
vector<int>v = { a[0] };
rep(i, n - 1)v.push_back(a[i + 1] - a[i]);
v.push_back(l - a[n - 1]);
int sz = v.size();
auto f = [&](int target)->bool {
vector<int>r(sz, -1);
int j = 0;
int sum = 0;
rep(i, sz) {
while (j < sz && sum < target) {
sum += v[j];
j++;
}
if (sum >= target)r[i] = j;
sum -= v[i];
}
vector<int>dp(sz);
rep(i, sz) {
if (r[i] == -1)dp[i] = INF;
else dp[i] = r[i] - i;
}
auto dp2 = dp;
rep(i, sz - 1) chmin(dp2[i], dp2[i + 1]);
int mn = INF;
rep(i, sz) {
if (r[i] == -1)continue;
if (r[i] == sz)continue;
int x = dp[i];
int y = dp2[r[i]];
chmin(mn, x + y);
}
return k + 1 <= 2 + sz - mn;
};
auto ans = kwm_t::algorithm::search::binarySearch(0, l, f);
cout << ans << endl;
return 0;
}