結果
問題 | No.733 分身並列コーディング |
ユーザー |
![]() |
提出日時 | 2018-09-07 22:22:38 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,082 ms / 1,500 ms |
コード長 | 793 bytes |
コンパイル時間 | 586 ms |
コンパイル使用メモリ | 57,460 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-29 15:24:57 |
合計ジャッジ時間 | 11,233 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
//TLEその2 #include <iostream> #include <algorithm> #define rep(i, n) for(i = 0; i < n; i++) using namespace std; int T, n; int t[17]; int dp[1 << 17]; int dfs(int rem) { int i, j; if (rem == 0) return 0; if (dp[rem] != -1) return dp[rem]; int id[17], cnt = 0; rep(i, n) { if ((rem >> i) & 1) { id[cnt++] = i; } } int ret = n; rep(i, (1 << (cnt - 1))) { int sumT = t[id[0]], sol = (1 << id[0]); rep(j, cnt - 1) { if ((i >> j) & 1) { sumT += t[id[j + 1]]; sol += (1 << id[j + 1]); } } if (sumT <= T) { int res = dfs(rem - sol) + 1; ret = min(ret, res); } } return dp[rem] = ret; } int main() { int i; cin >> T >> n; rep(i, n) cin >> t[i]; rep(i, (1 << n)) dp[i] = -1; int res = dfs((1 << n) - 1); cout << res << endl; return 0; }