結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
|
提出日時 | 2018-12-07 17:15:28 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 868 bytes |
コンパイル時間 | 1,444 ms |
コンパイル使用メモリ | 160,656 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 03:24:34 |
合計ジャッジ時間 | 2,802 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long ll; #define INF (1<<30) #define INFLL (1ll<<60) typedef pair<int, int> P; typedef pair<int, P> E; #define MOD (1000000007ll) #define l_ength size void mul_mod(ll& a, ll b){ a *= b; a %= MOD; } void add_mod(ll& a, ll b){ b += MOD; a += b; a %= MOD; } int n; ll memo[33400],m[20]; bool done[33400]; ll dp(int st){ int i; ll s=0ll; if(done[st]){ return memo[st]; } done[st] = true; for(i=0; i<n; ++i){ if(st&(1<<i)){ s += m[i]; } } for(i=0; i<n; ++i){ if(st&(1<<i)){ memo[st] = min(memo[st],dp(st-(1<<i))+max(0ll,m[i]-(s-m[i])%1000)); } } return memo[st]; } int main(void){ int i; fill(done,done+33400,false); fill(memo,memo+33400,INFLL); done[0] = true; memo[0] = 0ll; cin >> n; for(i=0; i<n; ++i){ cin >> m[i]; } cout << (dp((1<<n)-1)) << endl; return 0; }