結果
| 問題 |
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';
}