結果

問題 No.1701 half price
コンテスト
ユーザー ramia777
提出日時 2022-05-10 23:07:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 3,000 ms
コード長 2,885 bytes
コンパイル時間 886 ms
コンパイル使用メモリ 96,592 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 06:05:11
合計ジャッジ時間 1,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
// Yukicoder
// No.1701 half price




//二次元可変配列
//vector <vector <int>> mass;
//vector <vector <int>> memo;

//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>//list
#include <set> //tree
#include <map> //連想配列
#include <unordered_set> //hash
#include <unordered_map> //hash
#include <algorithm>
#include <iomanip>
#include <string>
#include <stdlib.h>


using namespace std;
typedef unsigned long long ULL;
typedef signed long long SLL;
typedef unsigned int UINT;


#define START (0)
#define RIGHT (1)
#define UP    (2)
#define LEFT  (3)
#define DOWN  (4)

#define DATA_MAX (1000000)
#define FMAX(a,b)  ((a)>(b)?(a):(b))
#define FMIN(a,b)  ((a)<(b)?(a):(b))


vector <vector <SLL>> memo2;
vector<SLL> memo1;
vector<SLL> c;
vector<SLL> v;
vector<SLL> dp;

SLL H ,A, B, T;

SLL N, W, comp;

UINT hashtable=0; //n番目の品物を選んだら1<<nをたてる。0なら1つも選んでいない状態


void PrintHashTable( void )
{
	//cout << hashtable << endl;
}


int func(SLL *data, SLL n, SLL ans)
{
	



	//1つ以上の商品を選んでいて、かつ値段の合計がW円の場合
	if ( hashtable && (ans == W))
	{
		//組み合わせなので、過去の組み合わせは省く
		if (v[hashtable] == 0)//過去一度もない組み合わせならば…
		{
			comp++; //答えをカウント
			v[hashtable] = 1; //この組み合わせは組み合わせ済として登録
			//cout << "return comp" << endl;
		}
		
		//PrintHashTable();
		//return 0;
	}

	if (ans > W)
	{
		//cout << "return W" << endl;
		//PrintHashTable();
		return 0;
	}

	if (n >= N)
	{
		//cout << "return N" << endl;
		//PrintHashTable();
		return 0;
	}


	//cout << "買わない場合：data=" << data[n] << ", n=" << n << ", ans=" << ans << endl;
	hashtable= hashtable & ~( 1 << (n + 1));
	func(data, n + 1, ans);

	//cout << "半額にして買う場合：data=" << data[n] << ", n=" << n << ", ans=" << ans << endl;
	hashtable = hashtable | (1 << (n + 1));
	func(data, n + 1, ans + data[n] / 2);

	//cout << "買う場合：data=" << data[n] << ", n=" << n << ", ans=" << ans << endl;
	hashtable = hashtable | (1 << (n + 1));
	func(data, n + 1, ans + data[n] );


	//1つ上の階層に戻るときはフラグをクリアしておく
	hashtable = hashtable & ~(1 << (n + 1));

	return 0;
}


int main(int argc, char *argv[])
{

	//char s[] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };
	//char ans[30];
	//float min = INFINITY;
	//SLL dp[5][35]; //DP 少し余裕をもって配列を確保

	SLL a[15];

	v.resize(17000); //ベクタ配列の初期化(2^14以上）

	cin >> N;
	cin >> W;

	for (int i=0;i<N;i++)
	{
		cin >> a[i];
	}

	func(&a[0], 0, 0);



	cout <<  comp << endl;

	///////////////////
	//cout << endl;
	//getchar();
	
	return 0; //end



}
0