結果

問題 No.286 Modulo Discount Store
コンテスト
ユーザー koyumeishi
提出日時 2015-10-10 00:27:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,275 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 488 ms
コンパイル使用メモリ 68,996 KB
最終ジャッジ日時 2024-11-14 19:18:39
合計ジャッジ時間 1,034 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:9: error: ‘function’ was not declared in this scope
   61 |         function<int(int)> dfs = [&](int state){
      |         ^~~~~~~~
main.cpp:11:1: note: ‘std::function’ is defined in header ‘<functional>’; did you forget to ‘#include <functional>’?
   10 | #include <set>
  +++ |+#include <functional>
   11 | using namespace std;
main.cpp:61:18: error: expected primary-expression before ‘int’
   61 |         function<int(int)> dfs = [&](int state){
      |                  ^~~
main.cpp:79:17: error: ‘dfs’ was not declared in this scope
   79 |         cout << dfs((1<<n)-1) << endl;
      |                 ^~~

ソースコード

diff #
raw source code 

#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;
}
0