結果

問題 No.286 Modulo Discount Store
ユーザー OUDON
提出日時 2017-09-29 23:58:23
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 502 ms
コード長 1,495 Byte
コンパイル時間 1,183 ms
使用メモリ 129,508 KB
最終ジャッジ日時 2019-07-12 05:28:40

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 48 ms
129,504 KB
case2.txt AC 51 ms
129,508 KB
case3.txt AC 148 ms
129,508 KB
case4.txt AC 49 ms
129,504 KB
case5.txt AC 49 ms
129,504 KB
case6.txt AC 48 ms
129,504 KB
case7.txt AC 265 ms
129,508 KB
case8.txt AC 48 ms
129,508 KB
case9.txt AC 48 ms
129,504 KB
case10.txt AC 48 ms
129,508 KB
case11.txt AC 95 ms
129,508 KB
case12.txt AC 49 ms
129,508 KB
case13.txt AC 48 ms
129,508 KB
case14.txt AC 148 ms
129,504 KB
case15.txt AC 48 ms
129,504 KB
case16.txt AC 47 ms
129,508 KB
case17.txt AC 50 ms
129,508 KB
case18.txt AC 502 ms
129,504 KB
case19.txt AC 95 ms
129,504 KB
case20.txt AC 47 ms
129,504 KB
case21.txt AC 58 ms
129,508 KB
case22.txt AC 48 ms
129,504 KB
case23.txt AC 48 ms
129,504 KB
case24.txt AC 153 ms
129,504 KB
case25.txt AC 53 ms
129,508 KB
case26.txt AC 73 ms
129,504 KB
case27.txt AC 58 ms
129,504 KB
case28.txt AC 75 ms
129,508 KB
case29.txt AC 285 ms
129,504 KB
case30.txt AC 55 ms
129,504 KB
case31.txt AC 50 ms
129,508 KB
case32.txt AC 55 ms
129,504 KB
case33.txt AC 55 ms
129,504 KB
case34.txt AC 49 ms
129,504 KB
case35.txt AC 53 ms
129,504 KB
case36.txt AC 51 ms
129,500 KB
case37.txt AC 49 ms
129,504 KB
case38.txt AC 70 ms
129,508 KB
case39.txt AC 49 ms
129,504 KB
case40.txt AC 263 ms
129,504 KB
sample1.txt AC 49 ms
129,508 KB
sample2.txt AC 48 ms
129,508 KB
sample3.txt AC 48 ms
129,508 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#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++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

const int MOD = 1000;
int dp[1<<15][1000];

int main()
{
    ios::sync_with_stdio(false);
    int N; cin >> N;

    fill(dp[0], dp[0] + (1<<15) * 1000, INF);
    dp[0][0] = 0;

    vector<int> M(N);
    int sum = 0;
    rep(i, N) { cin >> M[i]; sum += M[i]; }
    
    for (int i=0; i<(1<<N); i++) {
        for (int j=0; j<1000; j++) {
            for (int n=0; n<N; n++) {
                if (dp[i][j] < INF && !((i>>n)&1)) {
                    int m = M[n];
                    dp[i|(1<<n)][(j+m)%MOD] = min(dp[i|(1<<n)][(j+m)%MOD], dp[i][j] + max(0, m - j));
#ifdef DEBUG
                    // DUMP(BINARY(i));
                    // cerr << BINARY((i|(1<<n))) << endl;
                    // DUMP(j);
#endif
                }
            }
        }
    }

    // int ans = INF;
    // for (int j=0; j<=1000; j++) ans = min(ans, dp[(1<<N)-1][j]);
    cout << dp[(1<<N) - 1][sum%MOD] << endl;
} 
0