#52826 (C++11(old_compat)) No.286 Modulo Discount Store

• 問題: No.286 Modulo Discount Store
• ユーザー: koyumeishi
• 提出日時: 2015-10-10 00:27:51
• 言語: C++11(old_compat) (gcc 12.4.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 6 ms / 2,000 ms
• コード長: 1,275 bytes
• コンパイル時間: 1,362 ms
• コンパイル使用メモリ: 171,204 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2026-03-08 16:03:46
• 合計ジャッジ時間: 2,648 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 40

ソースコード

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

int bit_count(long long x){
	long long ret = 0;
	while(x){
		ret++;
		x -= x&-x;
	}
	return ret;
}


int main(){
	int n;
	cin >> n;
	vector<int> m(n);
	for(int i=0; i<n; i++){
		cin >> m[i];
	}

	vector<int> dp(1<<n, 1e8);

/*
	vector<vector<int>> bits(n+1);
	for(int i=0; i<(1<<n); i++){
		bits[bit_count(i)].push_back(i);
	}

	dp[0] = 0;
	for(int i=0; i<n; i++){
		for(int s: bits[i]){

			int x = 0;
			for(int k=0; k<n; k++){
				if((s>>k)&1){
					x += m[k];
				}
			}
			x %= 1000;

			for(int k=0; k<n; k++){
				if((s>>k)&1) continue;
				int& next = dp[s|(1<<k)];
				next = min(next, dp[s] + max(0, m[k]-x));
			}
		}
	}
	cout << dp[(1<<n)-1] << endl;
*/

	function<int(int)> dfs = [&](int state){
		if(state == 0) return 0;
		if(dp[state] != 1e8) return dp[state];

		int ret = 1e8;
		int x = 0;
		for(int i=0; i<n; i++){
			if(state&(1<<i)) x += m[i];
		}

		for(int i=0; i<n; i++){
			if(state&(1<<i)){
				ret = min( ret, dfs(state^(1<<i)) + max(m[i] - (x-m[i])%1000, 0) );
			}
		}
		return dp[state] = ret;
	};

	cout << dfs((1<<n)-1) << endl;


	return 0;
}