結果
問題 | No.3051 Make All Divisible |
ユーザー |
|
提出日時 | 2025-03-07 23:49:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 2,264 bytes |
コンパイル時間 | 681 ms |
コンパイル使用メモリ | 80,184 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 02:26:02 |
合計ジャッジ時間 | 2,998 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <algorithm> #include <iostream> using namespace std; typedef long long ll; typedef pair<ll, int> P; const ll INF = 8000000000000000000; void solve() { int n, k; cin >> n >> k; ll a[2005]; ll s = 0; for (int i = 0; i < n; i++) { cin >> a[i]; s += a[i] % k; } if (n == k) { for (int i = 0; i < n - 1; i++) { if (a[i] % k != a[i + 1] % k) { cout << -1 << endl; return; } } cout << a[0] % k << endl; return; } if (s % k) { cout << -1 << endl; return; } sort(a, a + n, greater<ll>()); ll x = 0; ll h = 0; ll ans = INF; for (int r = n; r > k; r--) { P p[4005]; ll s = x; for (int i = 0; i < r; i++) { p[i] = P(a[i] % k + (h / k) * k, i); if (p[i].first < h) { p[i].first += k; } s += p[i].first; } sort(p, p + r); int j; for (j = 0; j < r; j++) { if (p[j].second == r - 1) { break; } } for (int i = r; i < r * 2; i++) { p[i] = P(p[i - r].first + k, p[i - r].second); } bool g = false; for (int e = 0; e < r; e++) { ll y = (p[e + r - 1].first * k - s) / ((r - k) * k); if (y * ((r - k) * k) < p[e + r - 1].first * k - s) { y++; } if (y < 0) { continue; } bool f = true; if (j >= e && p[j].first + y * k > a[p[j].second]) { f = false; } if (j < e && p[j].first + k + y * k > a[p[j].second]) { f = false; } if (f) { g = true; ans = min(ans, (s + y * k * r) / k); } s += k; } x += a[r - 1]; h = a[r - 1]; } cout << (ans < INF ? ans : -1) << endl; } int main() { int t; cin >> t; while (t--) { solve(); } }