結果
問題 | No.733 分身並列コーディング |
ユーザー |
|
提出日時 | 2018-09-15 13:47:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 464 ms / 1,500 ms |
コード長 | 1,477 bytes |
コンパイル時間 | 1,340 ms |
コンパイル使用メモリ | 121,172 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-17 23:52:28 |
合計ジャッジ時間 | 10,696 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#define _USE_MATH_DEFINES #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <vector> #include <array> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <iterator> #include <memory> #include <regex> using namespace std; template <size_t T> bool prevSubset(bitset<T>& bs, const bitset<T>& mask) { if(bs.none()) return false; bs = bs.to_ulong() - 1ull; bs &= mask; return true; } const int INF = INT_MAX; int main() { int t, n; cin >> t >> n; vector<int> v(n); for(int i=0; i<n; ++i) cin >> v[i]; vector<bool> isCompleted(1<<n); for(int i=0; i<(1<<n); ++i){ bitset<17> bs(i); int sum = 0; for(int j=0; j<n; ++j){ if(bs[j]) sum += v[j]; } isCompleted[i] = (sum <= t); } vector<int> dp(1<<n, INF); dp.back() = 0; for(int i=(1<<n)-1; i>0; --i){ bitset<17> mask(i); bitset<17> bs = mask; do{ if(isCompleted[bs.to_ulong()]){ int j = (mask ^ bs).to_ulong(); dp[j] = min(dp[j], dp[i] + 1); } }while(prevSubset(bs, mask)); } cout << dp[0] << endl; return 0; }