結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
|
提出日時 | 2017-08-15 05:05:39 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 769 bytes |
コンパイル時間 | 2,154 ms |
コンパイル使用メモリ | 158,084 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 10:17:41 |
合計ジャッジ時間 | 2,780 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=a;i<b;i++) #define rep(i,b) FOR(i,0,b) #define INF mugen #define dump(x) cerr<<#x<<"="<<x<<endl using ll = long long; const ll mod = LLONG_MAX; int N,M[15],dp[(1<<15)]; int mask; bool contain(int mask,int pos){ if((mask&(1<<pos))!=0)return true; return false; } int main(){ cin>>N; rep(i,N)cin>>M[i]; memset(dp,0x3f,sizeof(dp)); dp[0]=0; for(int mask=0;mask<(1<<N);mask++){ for(int i=0;i<N;i++){ if(!contain(mask,i)){ int sum=0; for(int j=0;j<N;j++){ if(contain(mask,j))sum+=M[j]; } int plus=max(0,M[i]-(sum%1000)); dp[mask|(1<<i)]=min(dp[mask|(1<<i)],dp[mask]+plus); } } } cout<<dp[(1<<N)-1]<<endl; }