結果

問題 No.50 おもちゃ箱
コンテスト
ユーザー assy1028
提出日時 2015-03-24 13:38:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 243 ms / 5,000 ms
コード長 2,773 bytes
コンパイル時間 1,466 ms
コンパイル使用メモリ 109,612 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2024-06-25 20:54:48
合計ジャッジ時間 5,455 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:123:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  123 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:124:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  124 |     for (int i = 0; i < n; i++) scanf("%d", &as[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~
main.cpp:125:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  125 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
main.cpp:126:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  126 |     for (int i = 0; i < m; i++) scanf("%d", &bs[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <iomanip>
using namespace std;

#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define uniq(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef pair<int, int> P;
typedef unsigned int uint;
typedef unsigned long long ull;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};

const int inf = 1000000009;
const double eps = 1e-8;

int as[10], bs[10];
int n, m;
set<vector<int> > memo;
string to_binString(int val) {
    if (!val)
	return string("0");

    string ret;
    while(val != 0) {
	if ((val & 1) == 0)
	    ret.insert(ret.begin(), '0');
	else
	    ret.insert(ret.begin(), '1');
	val >>= 1;
    }
    return ret;
}

bool calc(int size, int pnum, int mini, int rem, int bit, vector<int>& vec) {
    if (pnum == size) {
	vector<int> h;
	for (int i = 0; i < size; i++) {
	    int sum = 0;
	    for (int j = 0; j < n; j++)
		if ((vec[i]>>j)&1)
		    sum += as[j];
	    h.push_back(sum);
	}
	sort(rall(h));
	for (int i = 0; i < size; i++) {
	    if (bs[m-i-1] < h[i])
		return false;
	}
	return true;
    } else {
	if (memo.count(vec) == 0) {
	    memo.insert(vec);
	    if (pnum == size-1) {
		vec.push_back(~bit);
		return calc(size, pnum+1, mini, 0, bit, vec);
	    } else {
		for (int i = mini; i * (size-pnum-1) <= rem-i; i++) {
		    //cout << size << " " << pnum << " " << i << endl;
		    int comb = (1 << i) - 1;
		    while (comb < 1 << n) {
			if ((comb&bit) == 0) {
			    //cout << to_binString(comb) << endl; 
			    vector<int> tv = vec;
			    tv.push_back(comb);
			    sort(all(tv));
			    if (calc(size,  pnum+1, i, rem-i, bit|comb, tv))
				return true;
			}
			int x = comb & -comb, y = comb + x;
			comb = ((comb & ~y) / x >> 1) | y;
		    }
		}
	    }
	}
	return false;
    }
}

int solve(int n, int m) {
    for (int i = 1; i <= m; i++) {
	memo.clear();
	vector<int> vec;
	if (calc(i, 0, 1, n, 0, vec))
	    return i;
    }
    return -1;
}

int main() {
    /*
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    */


    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &as[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d", &bs[i]);
    sort(bs, bs+m);
    printf("%d\n", solve(n, m));
}
0