結果
問題 | No.733 分身並列コーディング |
ユーザー |
|
提出日時 | 2018-09-07 22:53:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,024 ms / 1,500 ms |
コード長 | 1,269 bytes |
コンパイル時間 | 2,333 ms |
コンパイル使用メモリ | 196,768 KB |
最終ジャッジ日時 | 2025-01-06 13:02:54 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
//================================= // Created on: 2018/09/07 21:49:21 //================================= #include <bits/stdc++.h> #define show(x) std::cerr << #x << " = " << x << std::endl using ll = long long; int main() { int T, N; std::cin >> T >> N; std::vector<int> t(N); for (int i = 0; i < N; i++) { std::cin >> t[i]; } const int mask = 1 << N; constexpr int INF = 1 << 30; std::vector<int> sum(mask, 0); for (int i = 0; i < mask; i++) { for (int j = 0; j < N; j++) { if (i & (1 << j)) { sum[i] = sum[i - (1 << j)] + t[j]; break; } } } std::vector<int> dp(mask, INF); dp[0] = 0; for (int j = 1; j <= N; j++) { std::vector<int> tmp(mask, INF); for (int i = 0; i < mask; i++) { if (dp[i] > T) { continue; } const int comp = mask - i - 1; for (int j = comp; j > 0; j = (j - 1) & comp) { if (dp[i] > tmp[i + j] or sum[j] > std::min(T, tmp[i + j])) { continue; } tmp[i + j] = std::min(tmp[i + j], std::max(dp[i], sum[j])); } } dp = tmp; if (dp[mask - 1] <= T) { return std::cout << j << std::endl, 0; } } return 0; }