結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー seekworser
提出日時 2025-11-12 03:01:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 685 ms / 2,000 ms
コード長 2,378 bytes
記録
コンパイル時間 4,526 ms
コンパイル使用メモリ 276,208 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-03 23:31:26
合計ジャッジ時間 16,951 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i, n) for (ll i=0; i<(n); i++)

// https://kenkoooo.hatenablog.com/entry/2016/11/30/163533
using lll = __int128_t;
std::istream &operator>>(std::istream &src, lll &value) {
    ll x; src >> x;
    value = x;
    return src;
}
std::ostream &operator<<(std::ostream &dest, lll value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
lll INF = ((lll)(1) << 125);

lll parse(string &s) {
  lll ret = 0;
  for (int i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
  return ret;
}

void solve() {
    lll n,m,a,b,c,d; cin >> n >> m >> a >> b >> c >> d;
    auto eval = [&] (lll n, lll m, lll a, lll b, lll c, lll d, lll x) -> lll {return a * x + b * ((c * x + d) / m);};
    auto f = [&] (auto self, lll n, lll m, lll a, lll b, lll c, lll d) -> lll {
        if (n <= 0) return -INF;
        if (a >= 0 && b >= 0) { return eval(n, m, a, b, c, d, n-1); }
        if (a <= 0 && b <= 0) { return eval(n, m, a, b, c, d, 0); }
        if (m == 1) {
            if (a + b * c >= 0) return a * (n-1) + b * c * (n-1) + b * d;
            return b * d;
        }
        if (c >= m) {
            lll c1 = c / m;
            lll c2 = c % m;
            return self(self, n, m, a + b * c1, b, c2, d);
        }
        if (d >= m) {
            lll d1 = d / m;
            lll d2 = d % m;
            return self(self, n, m, a, b, c, d2) + b * d1;
        }
        if (a < 0) {
            lll k = (c * (n-1) + d) / m;
            lll ans = self(self, k, c, b, a, m, m - d + c - 1) + b;
            return max(ans, eval(n, m, a, b, c, d, 0));
        } else {
            lll k = (c * (n-1) + d) / m;
            lll ans = self(self, k, c, b, a, m, m - d - 1);
            return max(ans, eval(n, m, a, b, c, d, n-1));
        }
    };
    lll ans = f(f, n, m, a, b, c, d);
    cout << ans << '\n';
}

int main() {
    ll t; cin >> t;
    rep(i, t) solve();
}
0