結果
問題 | No.1701 half price |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
//// 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}