結果
問題 |
No.733 分身並列コーディング
|
ユーザー |
![]() |
提出日時 | 2022-07-01 17:53:40 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 1,500 ms |
コード長 | 1,044 bytes |
コンパイル時間 | 3,925 ms |
コンパイル使用メモリ | 141,792 KB |
実行使用メモリ | 13,208 KB |
最終ジャッジ日時 | 2024-11-25 22:38:02 |
合計ジャッジ時間 | 6,080 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; int main() { int T; cin >> T; int N; cin >> N; vector<int> times(N); for (int i = 0; i < N; ++i) { cin >> times[i]; } int L = 1 << N; int dp[L][N + 2]; memset(dp, 0, sizeof(dp)); for (int mask = 1; mask < L; ++mask) { for (int i = 0; i <= N; ++i) { dp[mask][i] = T * N + 1; } } for (int mask = 1; mask < L; ++mask) { for (int i = 0; i < N; ++i) { if (mask >> i & 1) { for (int j = 0; j <= N; ++j) { int nmask = mask ^ (1 << i); dp[mask][j] = min(dp[mask][j], dp[nmask][j] + times[i]); if (dp[mask][j] <= T) { dp[mask][j + 1] = 0; } } } } } for (int i = 0; i <= N; ++i) { if (!dp[L - 1][i]) { cout << i << endl; break; } } return 0; }