結果

問題 No.50 おもちゃ箱
コンテスト
ユーザー myanta
提出日時 2017-05-10 23:35:38
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 791 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,492 ms
コンパイル使用メモリ 173,240 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:11:19
合計ジャッジ時間 2,583 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:52:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |                 for(i=0;i<n;i++) scanf("%d", &a[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp:54:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 |                 scanf("%d", &m);
      |                 ~~~~~^~~~~~~~~~
main.cpp:56:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |                 for(i=0;i<m;i++) scanf("%d", &b[i]);
      |                                  ~~~~~^~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<cstdio>
#include<vector>
#include<algorithm>


using namespace std;
using vi=vector<int>;


int solve_r(vi& a, vi& b, int d)
{
	if(d>=a.size())
	{
		return 1;
	}

	for(int i=0;i<b.size();i++)
	{
		if(a[d]>b[i]) continue;

		b[i]-=a[d];
		if(solve_r(a, b, d+1)) return 1;
		b[i]+=a[d];
	}
	return 0;
}


int solve(vi& a, vi b)
{
	vi c;

	for(int i=1;i<=b.size();i++)
	{
		c=b;
		c.resize(i);
		if(solve_r(a, c, 0)) return i;
	}

	return -1;
}


int main(void)
{
	int  n, m, i;
	vi a, b;

	while(scanf("%d", &n)==1)
	{
		a.resize(n);
		for(i=0;i<n;i++) scanf("%d", &a[i]);

		scanf("%d", &m);
		b.resize(m);
		for(i=0;i<m;i++) scanf("%d", &b[i]);

		sort(a.begin(), a.end(), greater<int>());
		sort(b.begin(), b.end(), greater<int>());
		printf("%d\n", solve(a, b));
	}

	return 0;
}
0