結果

問題 No.1701 half price
ユーザー ramia777ramia777
提出日時 2022-05-10 14:50:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,670 bytes
コンパイル時間 796 ms
コンパイル使用メモリ 96,896 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-17 20:44:26
合計ジャッジ時間 1,678 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 14 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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;

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


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

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

	if (ans == W)
	{
		//組み合わせなので、過去の組み合わせは省く
		if (v[hashtable] == 0)//過去一度もない組み合わせならば…
		{
			comp++; //答えをカウント
			v[hashtable] = 1; //この組み合わせは組み合わせ済として登録
		}
		//cout << "return comp" << endl;
		//PrintHashTable();
		return 1;
	}
	
	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(100000); //ベクタ配列の初期化

	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