結果
問題 | No.733 分身並列コーディング |
ユーザー |
![]() |
提出日時 | 2020-06-13 15:46:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 1,500 ms |
コード長 | 1,028 bytes |
コンパイル時間 | 962 ms |
コンパイル使用メモリ | 83,132 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 12:50:14 |
合計ジャッジ時間 | 6,452 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; int T, N, t[20]; int dp[1<<17]; int cnt_bit(int m){ int ans = 0; for(int i = 0; i < N; i++){ if(m&(1<<i)) ans++; } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> T >> N; for(int i = 0; i < (1<<N); i++) dp[i] = 30; for(int i = 0; i < N; i++) cin >> t[i]; for(int i = 0; i < N; i++){ dp[1<<i] = 1; } for(int i = 1; i < (1<<N); i++){ int sum = 0; for(int j = 0; j < N; j++){ if(i&(1<<j)) sum += t[j]; } if(sum <= T) dp[i] = 1; } for(int i = 1; i < (1<<N); i++){ if(cnt_bit(i) <= 1) continue; for(int j = (i-1)&i; j >= 1; j = (j-1)&i){ int m = i-j; dp[i] = min(dp[i], dp[j]+dp[m]); } } cout << dp[(1<<N)-1] << endl; }