結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2018-06-20 12:12:02 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 856 bytes |
コンパイル時間 | 702 ms |
コンパイル使用メモリ | 82,884 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 17:24:13 |
合計ジャッジ時間 | 1,897 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include<algorithm> #include<iomanip> #include<queue> #include<deque> #include<map> #include<bitset> #include<math.h> #include<string> using namespace std; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define REP(i,m,n) for(int i=m;i<(int)(n);i++) typedef long long ll; typedef pair<int,int> pint; const ll mod= 1e9+7; const int inf=1e9+7; const ll longinf = 1LL<<60; int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1}; int dp[101010],sum[101010]; int main(){ int n;cin>>n; int a[n]; rep(i,n)cin>>a[i]; int all=1<<n; rep(i,all)rep(j,n) if(i&(1<<j))sum[i]+=a[j]; rep(i,all)dp[i]=inf; dp[0]=0; rep(i,all){ rep(j,n){ if(i&(1<<j)){ int res=dp[i^(1<<j)]; res+=max(0,a[j]-sum[i^(1<<j)]%1000); dp[i]=min(res,dp[i]); } } } cout<<dp[all-1]<<endl; return 0; }