結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2015-10-10 07:17:05 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 1,073 bytes |
コンパイル時間 | 1,358 ms |
コンパイル使用メモリ | 160,868 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 04:57:08 |
合計ジャッジ時間 | 2,608 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #define mp make_pair #define mt make_tuple #define pb push_back #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<long,long> pll; const int INF=1<<29; const double EPS=1e-9; const int MOD = 100000007; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; int N; vector<int> M; ll dp[1 << 16]; ll memo(int bit){ if (__builtin_popcount(bit) == N){ return 0; } ll &res = dp[bit]; if (res >= 0){ return res; } res = INF; ll tmp = 0; vector<int> next; for (int j = 0; j < N; j++){ if (bit >> j & 1){ tmp += M[j]; }else{ next.push_back(j); } } tmp = tmp % 1000; for (int i = 0; i < next.size(); i++){ res = min(res, memo(bit | 1 << next[i]) + max(M[next[i]] - tmp, 0LL)); } return res; } int main(){ cin >> N; M.resize(N); for (int i = 0; i < N; i++){ cin >> M[i]; } memset(dp, -1, sizeof(dp)); cout << memo(0) << endl; }