結果
問題 | No.2694 The Early Bird Catches The Worm |
ユーザー |
|
提出日時 | 2024-03-22 22:58:11 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 4,964 bytes |
コンパイル時間 | 1,455 ms |
コンパイル使用メモリ | 133,572 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-09-30 12:20:27 |
合計ジャッジ時間 | 5,759 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 72 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <cstring>#include <ctime>#include <deque>#include <iomanip>#include <iostream>#include <iterator>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>#include <vector>template <typename T1, typename T2>std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {os << p.first << " " << p.second;return os;}template <typename T1, typename T2>std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {is >> p.first >> p.second;return is;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {for (int i = 0; i < (int)v.size(); i++) {os << v[i] << (i + 1 != (int)v.size() ? " " : "");}return os;}template <typename T>std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (T &in : v) is >> in;return is;}template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if ((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt &operator^=(long long p) { // quick_pow here:3ModInt res = 1;for (; p; p >>= 1) {if (p & 1) res *= *this;*this *= *this;}return *this = res;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }ModInt operator^(long long p) const { return ModInt(*this) ^= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }explicit operator int() const { return x; } // added by QCFiumModInt operator=(const int p) {x = p;return ModInt(*this);} // added by QCFiumModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;std::swap(a, b);u -= t * v;std::swap(u, v);}return ModInt(u);}friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &p) {return os << p.x;}friend std::istream &operator>>(std::istream &is, ModInt<mod> &a) {long long x;is >> x;a = ModInt<mod>(x);return (is);}};using mint = ModInt<998244353>;const int MOD = 998244353;template <typename T>std::pair<std::vector<T>, std::vector<T>> get_prime_factor_with_kinds(T n) {std::vector<T> prime_factors;std::vector<T> cnt; // number of i_th factorfor (T i = 2; i * i <= n; i++) {if (n % i == 0) {prime_factors.push_back(i);cnt.push_back(0);while (n % i == 0) n /= i, cnt[(int)prime_factors.size() - 1]++;}}if (n > 1) prime_factors.push_back(n), cnt.push_back(1);assert(prime_factors.size() == cnt.size());return {prime_factors, cnt};}template <typename T>std::vector<T> get_divisors(T x, bool sorted = true) {std::vector<T> res;for (T i = 1; i <= x / i; i++)if (x % i == 0) {res.push_back(i);if (i != x / i) res.push_back(x / i);}if (sorted) std::sort(res.begin(), res.end());return res;}void solve() {int n, h;std::cin >> n >> h;std::vector<long long> a(n), b(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}for (int i = 0; i < n; i++) {std::cin >> b[i];}long long ans = 0;std::vector<long long> prefix(n + 1), bjj(n + 1), pa(n + 1);for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + b[i];bjj[i + 1] = bjj[i] + 1LL * b[i] * (i + 1);pa[i + 1] = pa[i] + a[i];}for (int i = 0; i < n; i++) {int r = n - 1;int l = i;auto check = [&](int mid) -> long long {long long sum = prefix[mid + 1] - prefix[i];sum += bjj[mid + 1] - bjj[i];sum -= 1LL * (i + 1) * (prefix[mid + 1] - prefix[i]);return sum;};while (l < r) {int mid = (l + r + 1) / 2;if (check(mid) <= h) {l = mid;} else {r = mid - 1;}}if (check(r) <= h) {ans = std::max(ans, pa[r + 1] - pa[i]);}}std::cout << ans << std::endl;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}}