結果
問題 | No.286 Modulo Discount Store |
ユーザー |
![]() |
提出日時 | 2017-03-19 11:22:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 570 bytes |
コンパイル時間 | 1,468 ms |
コンパイル使用メモリ | 167,196 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 23:32:44 |
合計ジャッジ時間 | 2,527 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #define REP(i,n,N) for(int i=n;i<N;i++) #define p(S) cout<<(S)<<endl #define ck(n,a,b) (a<=(n)&&(n)<b) typedef long long ll; using namespace std; int dp[1<<15]; int main(){ int N; int M[16]; cin>>N; REP(i,0,N){ cin>>M[i]; } REP(i,0,1<<N) dp[i]=1e8; int money[1<<15]; REP(i,0,1<<N) money[i]=0; REP(i,0,1<<N){ REP(j,0,N){ if(i&1<<j) money[i]+=M[j]; } money[i]%=1000; } dp[0]=0; REP(st,0,1<<N){ REP(i,0,N){ dp[st]=min(dp[st],max(dp[st^(1<<i)],dp[st^(1<<i)]+M[i]-money[st^(1<<i)])); } } p(dp[(1<<N)-1]); return 0; }