結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2019-06-28 22:33:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 703 bytes |
コンパイル時間 | 1,566 ms |
コンパイル使用メモリ | 167,716 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-02 04:57:08 |
合計ジャッジ時間 | 3,083 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; int M[N]; for (int i = 0; i < N; i++) { cin >> M[i]; } int dp[1<<N]; for (int i = 0; i < (1<<N); i++) { dp[i] = 100000000; } dp[0] = 0; for (int i = 0; i < (1<<N); i++) { int cost = 0; for (int j = 0; j < N; j++) { if ((i & (1<<j)) != 0) { cost += M[j]; } } cost %= 1000; for (int j = 0; j < N; j++) { if ((i & (1<<j)) == 0) { int idx = i | (1<<j); dp[idx] = min(dp[idx], dp[i] + max(0, M[j] - cost)); } } } cout << dp[(1<<N) - 1] << "\n"; return 0; }