結果
問題 | No.286 Modulo Discount Store |
ユーザー |
|
提出日時 | 2017-10-06 15:46:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 914 bytes |
コンパイル時間 | 654 ms |
コンパイル使用メモリ | 57,596 KB |
実行使用メモリ | 5,504 KB |
最終ジャッジ日時 | 2024-11-17 00:31:20 |
合計ジャッジ時間 | 2,150 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include<iostream> #include<string.h> using namespace std; const int kind = 1 << 15; int dp[15+1][kind + 1]; int main(){ memset(dp,0,sizeof(dp)); int n; cin >> n; int m[15]; for(int i = 0;i < n;i++){ cin >> m[i]; } for(int i = 0;i < n;i++){ dp[1][0+(1 << i)] = m[i]; } for(int i = 1;i < n;i++){ for(int j = 0;j < (1 <<n);j++){ if(dp[i][j] != 0){ for(int k = 0;k < n;k++){ if((j >> k) % 2 == 0){ int dis=0; for(int l = 0;l < n;l++){ if((j >> l) % 2 == 1) dis += m[l]; } dis = dis % 1000; if(dp[i+1][j + (1 << k)] != 0){ dp[i+1][j + (1 << k)] = min(dp[i+1][j + (1 << k)],dp[i][j] + max(0,m[k]-dis)); }else{ dp[i+1][j + (1 << k)] = dp[i][j] + max(0,m[k]-dis); } } } } } } int ans = 1e9; for(int i = 0;i < 1<<n;i++){ if(dp[n][i] != 0)ans = min(ans,dp[n][i]); } cout << ans << endl; return 0; }