結果

問題 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; //n1<<n01
void PrintHashTable( void )
{
//cout << hashtable << endl;
}
int func(SLL *data, SLL n, SLL ans)
{
//1W
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
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0