結果
問題 | No.286 Modulo Discount Store |
ユーザー |
![]() |
提出日時 | 2016-05-13 23:43:53 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 740 bytes |
コンパイル時間 | 1,299 ms |
コンパイル使用メモリ | 159,392 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-05 18:23:31 |
合計ジャッジ時間 | 2,609 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #define INF 1<<30 using namespace std; int dp[1<<20]; int a[1111]; int main(){ int n; cin >> n; for(int i=0;i<n;i++){ cin >> a[i]; } for(int i=0;i<(1<<n);i++){ dp[i]=1<<20; } dp[0]=0;//一番先頭には0を入れておく for(int i=0;i<(1<<n)-1;i++){ int ret=0; for(int j=0;j<n;j++){ if((i&(1<<j))){//そこの商品は買った ret+=a[j]; } } ret%=1000; for(int j=0;j<n;j++){ if((i&(1<<j))==0){//そこの商品はまだ買っていない /*すでにそこの商品を買った場合と、今から買う場合の最小値を選択*/ dp[i | (1<<j)] = min(dp[i | (1<<j)],dp[i]+max(0,a[j]-ret)); } } } cout << dp[(1<<n)-1] << endl; }