結果
問題 | No.286 Modulo Discount Store |
ユーザー |
![]() |
提出日時 | 2021-05-13 00:26:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 998 bytes |
コンパイル時間 | 1,904 ms |
コンパイル使用メモリ | 198,784 KB |
最終ジャッジ日時 | 2025-01-21 10:22:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
//https://ncode.syosetu.com/n4830bu/286/ #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> M(N); for (auto&& m : M) { cin >> m; } vector maine(1 << N, vector(N, 100000000)); vector<int> SUM(1 << N); for (int bit = 1; bit < (1 << N); bit++) { for (int i = 0; i < N; i++) { if (bit == (1 << i)) { maine[bit][i] = M[i]; SUM[bit] = M[i]; } else if (bit & (1 << i)) { SUM[bit] = SUM[bit ^ (1 << i)] + M[i]; for (int j = 0; j < N; j++) { if ((bit ^ (1 << i)) & (1 << j)) { maine[bit][i] = min(maine[bit][i], maine[bit ^ (1 << i)][j] + max(0, M[i] - (SUM[bit ^ (1 << i)] % 1000))); } } } } } int ans = 1e9; for (int i = 0; i < N; i++) { ans = min(ans, maine[(1 << N) - 1][i]); } cout << ans << endl; }