結果
問題 |
No.733 分身並列コーディング
|
ユーザー |
|
提出日時 | 2025-10-04 23:55:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,500 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 2,098 ms |
コンパイル使用メモリ | 204,036 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-04 23:55:49 |
合計ジャッジ時間 | 3,980 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int n; ll T; vector<ll> a; bool dfs_pack(int idx, vector<ll>& bins) { if (idx == n) return true; ll cur = a[idx]; int k = bins.size(); for (int j = 0; j < k; ++j) { if (bins[j] + cur <= T) { bool skip = false; for (int s = 0; s < j; ++s) if (bins[s] == bins[j]) { skip = true; break; } if (skip) continue; bins[j] += cur; if (dfs_pack(idx + 1, bins)) return true; bins[j] -= cur; if (bins[j] == 0) break; } } return false; } bool can_pack_with_k(int k) { ll sum = 0; for (ll v : a) sum += v; if (sum > (ll)k * T) return false; vector<ll> bins(k, 0); return dfs_pack(0, bins); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> T; cin >> n; a.resize(n); for (int i = 0; i < n; ++i) cin >> a[i]; ll mx = *max_element(a.begin(), a.end()); if (mx > T) { cout << -1 << '\n'; return 0; } ll sum = 0; for (ll v : a) sum += v; int low = max(1LL, (sum + T - 1) / T); int high = n; sort(a.rbegin(), a.rend()); int ans = high; while (low <= high) { int mid = (low + high) / 2; if (can_pack_with_k(mid)) { ans = mid; high = mid - 1; } else low = mid + 1; } cout << ans << '\n'; }