結果
| 問題 | No.3681 心の沸騰石 |
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-09-05 13:33:04 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| + 328µs | |
| コード長 | 3,745 bytes |
| 記録 | |
| コンパイル時間 | 1,985 ms |
| コンパイル使用メモリ | 334,052 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-09-05 13:33:18 |
| 合計ジャッジ時間 | 3,486 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 13 |
ソースコード
#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>
namespace kwm_t::algorithm::search {
/**
* @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:
*
*/
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:
*
*/
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);
long long r, p, q; cin >> r >> p >> q;
vector<long long>col(4);
rep(i, 4)cin >> col[i];
auto f = [&](const long long x)->bool {
long long cost = 0;
long long husoku = 0;
long long amari = col[3];
rep(i, 3) husoku += max(0LL, x - col[i]);
rep(i, 3) amari += max(0LL, col[i] - x);
if (husoku > amari)return false;
cost += x * p;
cost += husoku * q;
return cost <= r;
};
//f(18908650); return 0;
auto ans = kwm_t::algorithm::search::binarySearch<long long>(0, (long long)INF * 5, f);
cout << ans << endl;
return 0;
}