#2640 (C++11) No.50 おもちゃ箱

• 問題: No.50 おもちゃ箱
• ユーザー: ciel
• 提出日時: 2014-11-16 21:22:59
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 79 ms / 5,000 ms
• コード長: 649 bytes
• コンパイル時間: 721 ms
• コンパイル使用メモリ: 71,456 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-25 20:45:29
• 合計ジャッジ時間: 2,296 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	12 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	10 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	34 ms; 5,376 KB
testcase_18	AC	5 ms; 5,376 KB
testcase_19	AC	20 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	3 ms; 5,376 KB
testcase_22	AC	44 ms; 5,376 KB
testcase_23	AC	3 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	8 ms; 5,376 KB
testcase_29	AC	8 ms; 5,376 KB
testcase_30	AC	79 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	15 ms; 5,376 KB
testcase_33	AC	49 ms; 5,376 KB
testcase_34	AC	2 ms; 5,376 KB
testcase_35	AC	29 ms; 5,376 KB
testcase_36	AC	16 ms; 5,376 KB
testcase_37	AC	10 ms; 5,376 KB
testcase_38	AC	5 ms; 5,376 KB
testcase_39	AC	9 ms; 5,376 KB
testcase_40	AC	55 ms; 5,376 KB
testcase_41	AC	2 ms; 5,376 KB

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:8:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    8 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
main.cpp:10:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   10 |         for(int i=0;i<N;i++)scanf("%d",&a[i]);
      |                             ~~~~~^~~~~~~~~~~~
main.cpp:11:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   11 |         scanf("%d",&M);
      |         ~~~~~^~~~~~~~~
main.cpp:13:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 |         for(int i=0;i<M;i++)scanf("%d",&b[i]);
      |                             ~~~~~^~~~~~~~~~~~

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main(){
	int N,M;
	scanf("%d",&N);
	vector<int>a(N);
	for(int i=0;i<N;i++)scanf("%d",&a[i]);
	scanf("%d",&M);
	vector<int>b(M);
	for(int i=0;i<M;i++)scanf("%d",&b[i]);
	sort(a.begin(),a.end());
	sort(b.begin(),b.end(),greater<int>());
	int result=M+1;
	do{
		int cur=0,s=0;
		for(int i=0;i<a.size();i++){
			for(;cur<b.size()&&s+a[i]>b[cur];s=0,cur++);
			if(cur==b.size())break;
			s+=a[i];
		}
		cur++;
		if(result>cur)result=cur;
	}while(next_permutation(a.begin(),a.end()));
	printf("%d\n",result>M?-1:result);
}