結果

問題 No.3051 Make All Divisible
ユーザー SnowBeenDiding
提出日時 2025-03-07 22:57:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,613 bytes
コンパイル時間 6,060 ms
コンパイル使用メモリ 332,728 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-07 22:57:37
合計ジャッジ時間 7,550 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

using mint = modint998244353;

// void solve() {
//     int n;
//     cin >> n;
//     vector<int> a(n);
//     rep(i, 0, n) {
//         cin >> a[i];
//         if (a[i] > 0)
//             a[i]--;
//     }
//     mint ans = 0;
//     cout << ans.val() << endl;
// }

template <typename T> T ceil_div(T a, T b) {
    if (b < 0)
        a = -a, b = -b;
    return (a >= 0 ? (a + b - 1) / b : a / b);
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i];
    {
        ll sm = 0;
        rep(i, 0, n) { sm += a[i]; }
        if (sm % k != 0) {
            cout << "-1\n";
            return;
        }
    }
    vector<int> b(n);
    rep(i, 0, n) { b[i] = a[i] % k; }
    sort(b.begin(), b.end());
    if (b.back() == 0) {
        cout << "0\n";
        return;
    }
    int las = b.back();
    int smbp = 0;
    rep(i, 0, n - 1) { smbp += b[i]; }
    if (ceil_div(smbp, k - 1) >= las) {
        cout << (smbp + las) / k << '\n';
        return;
    }
    auto f = [&]() {
        int m = las + k;
        ll sm = 0;
        rep(i, 0, n) { sm += min(a[i], (ll)m); }
        return sm >= (ll)m * (ll)k;
    };
    bool ok = f();
    if (!ok) {
        cout << "-1\n";
        return;
    }
    cout << max((smbp + las) / k, las + k) << '\n';
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
0