結果

問題 No.286 Modulo Discount Store
コンテスト
ユーザー amaridekinai
提出日時 2019-09-17 18:30:59
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,053 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,411 ms
コンパイル使用メモリ 168,276 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-07 13:21:30
合計ジャッジ時間 2,384 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
void chmax(int &a, int b){ if( a < b){ swap(a,b);} return ;}
const int MAX_N = 1<<16;
int dp[MAX_N];

int pre[20][20];

void chmin( int & a, int b){ if( a > b){ swap(a,b);} return ;}

int main(){
  int N; cin >> N; 
  vector<int> M(N);
  for(int i = 0; i < N; i++){ cin >> M[i];}
  
  for(int i = 0; i < MAX_N; i++){ dp[i] = inf;}
  dp[0] = 0; //何も商品を買わない時は、当然0円
  
  for(int mask = 0; mask < (1<<N); mask++){
    //ビットが立っている時、すでに購入済みのことを示す
    for(int a = 0; a < N; a++){
      //次に、商品aを購入する場合を考える
      if( !(mask >> a & 1)){
        
       int res = 0;
       for(int b = 0; b < N; b++){//今まで買ったことのある分を問題文の通り考える
         if( mask >> b & 1 ){ res += M[b];} res %= 1000;
       }
      
      chmin(dp[mask+(1<<a)],dp[mask]+(max(M[a]-res,0))%1000);}
  }
}

cout << dp[(1<<N)-1] << endl; return 0;}
0