結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー Araya Luanseng
提出日時 2026-07-19 22:03:09
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 1,819 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,390 ms
コンパイル使用メモリ 350,700 KB
実行使用メモリ 1,306,496 KB
最終ジャッジ日時 2026-07-19 22:03:24
合計ジャッジ時間 7,130 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;
typedef __int128 ll;

constexpr ll INF = 1e36;

// ll floordiv(ll x, ll y) {
//     return x >= 0 ? x/y : -((-x)/y);
// }

ll solve(ll N, ll M, ll A, ll B, ll C, ll D) {
    // cout << N << " " << M << " " << A << " " << B << " " << C << " " << D << '\n';
    ll at_zero = B*(D/M);
    if (N <= 0) return -INF;
    if (N == 1) return at_zero;
    
    if (C == 0 || M == 1) {
        return max(at_zero, A*(N-1) + B*((C*(N-1) + D)/M));
    }
    
    if (A < 0) {
        // left endpoint
        ll nxt_N = (C*(N-1)+D)/M - D/M;
        
        if (nxt_N == 0) {
            return at_zero;
        }
        
        // cout << -A*additional << "\n";
        
        return max(
            at_zero,
            B*(D/M + 1) + solve(nxt_N, C, B, A, M, M*(D/M + 1) - D + C - 1)
        );
    } else {
        // right endpoint
        ll nxt_N = (C*(N-1)+D)/M;
        ll nxt_M = C;
        ll nxt_C = M;
        ll nxt_D = M-D-1;
        ll additional = 0;
        
        if (nxt_D < 0) {
            additional = (-nxt_D)/nxt_M + 1;
            nxt_D += additional*nxt_M;
        } else {
            additional = nxt_D/nxt_M;
            nxt_D -= nxt_M*additional;
            additional = -additional;
        }
        
        // cout << -A*additional << "\n";
        
        return max(
            A*(N-1) + B*((C*(N-1) + D) / M),
            solve(nxt_N, nxt_M, B + A*(nxt_C/nxt_M), A, nxt_C%nxt_M, nxt_D) - A*additional
        );
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    while (T--) {
        long long N, M, A, B, C, D;
        cin >> N >> M >> A >> B >> C >> D;
        cout << (long long)solve(N, M, A, B, C, D) << "\n";
        // cout << "===\n";
    }
    
    return 0;
}
0