結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-29 00:53:29
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 223 ms / 2,000 ms
コード長 2,561 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,075 ms
コンパイル使用メモリ 71,032 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-03 23:36:18
合計ジャッジ時間 5,922 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cassert> // assert
#include <iostream> // cin, cout, ios
#include <utility> // swap, pair

using ll = long long;

template <typename T> bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T> constexpr std::pair<T, T> divmod(T a, T b) {
    T q = a / b;
    T r = a % b;
    return {q, r};
}

// 商を無限大方向に切り下げる除算(剰余が0でない時の符号は除数の符号に一致)
template <typename T> constexpr std::pair<T, T> divmod_floor(T a, T b) {
    // 標準の truncating 除算を使う
    T q = a / b;
    T r = a % b;
    // もし符号が食い違っていたら 1 調整
    if ((r != 0) && ((r > 0) != (b > 0))) {
        q -= 1;
        r += b;
    }
    return {q, r};
}

// 剰余が非負になる除算（ユークリッド除算）
template <typename T> constexpr std::pair<T, T> divmod_euclid(T a, T b) {
    // 標準の truncating 除算を使う
    T q = a / b;
    T r = a % b;
    // 剰余が負なら 1 調整
    if (r < 0) {
        if (b > 0) {
            q -= 1;
            r += b;
        } else {
            q += 1;
            r -= b;
        }
    }
    return {q, r};
}

/**
    Max Weighted Floor (mwf) の再帰実装。
      mwf(l,r,m,a,b,c,d) = max_{l <= x < r} a*x + b*floor((c*x + d)/m)

    前提:
      - l < r, 0 < m

    計算量/メモリ:
      - 時間: O(log m)（ユークリッド互除法的再帰による構造縮約）
*/
template <typename T> T mwf(T l, T r, T m, T a, T b, T c, T d) {
    assert(l < r && 0 < m);
    T n = r - l;
    const auto [qc0, rc0] = divmod_euclid<T>(c, m);
    c = rc0;
    a += b * qc0;
    const auto [qd0, rd0] = divmod_euclid<T>(c * l + d, m);
    d = rd0;
    T sum_acc = a * l + b * qd0;
    assert(0 < n && 0 < m && 0 <= c && c < m && 0 <= d && d < m);
    n -= 1;
    const T y_max = (c * n + d) / m;
    T max_acc = sum_acc;
    chmax<T>(max_acc, sum_acc + a * n + b * y_max);
    if ((a <= 0 && b <= 0) || (a >= 0 && b >= 0) || y_max == 0) {
        return max_acc;
    }
    if (a < 0) {
        sum_acc += a + b;
    }
    chmax<T>(max_acc, mwf<T>(0, y_max, c, b, a, m, m - d - 1) + sum_acc);
    return max_acc;
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int t;
    ll n, m, a, b, c, d, ans;
    std::cin >> t;
    for(int i = 0; i < t; i++) {
        std::cin >> n >> m >> a >> b >> c >> d;
        assert(0 < n && 0 < m);
        ans = mwf<ll>(0, n, m, a, b, c, d);
        std::cout << ans << '\n';
    }
}
0