結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2014-12-08 21:17:16 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 1,008 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 35,172 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 20:45:30 |
合計ジャッジ時間 | 1,455 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:11:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 11 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:12:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 12 | for(int i=0;i<N;i++){scanf("%d", A+i);} | ~~~~~^~~~~~~~~~~ main.cpp:13:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 13 | scanf("%d", &M); | ~~~~~^~~~~~~~~~ main.cpp:14:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 14 | for(int i=0;i<M;i++){scanf("%d", B+i);} | ~~~~~^~~~~~~~~~~
ソースコード
#include <cstdio> #include <algorithm> int N, M; int A[10], B[10]; int cost[1<<10]; int dp[11][1<<10]; int main(){ scanf("%d", &N); for(int i=0;i<N;i++){scanf("%d", A+i);} scanf("%d", &M); for(int i=0;i<M;i++){scanf("%d", B+i);} for(int i=0;i<(1<<N);i++){ int c = 0; for(int j=0;j<N;j++){ if(i >> j & 1){ c += A[j]; } } cost[i] = c; } std::fill(&dp[0][0], &dp[0][0]+11*(1<<10), 100); dp[0][0] = 0; for(int i=0;i<M;i++){ for(int j=0;j<(1<<N);j++){ dp[i+1][j] = std::min(dp[i+1][j], dp[i][j]); for(int k=0;k<(1<<N);k++){ if(j & k){continue;} if(cost[k] > B[i]){continue;} dp[i+1][j|k] = std::min(dp[i+1][j|k], dp[i][j] + 1); } } } if(dp[M][(1<<N)-1] < 100){ printf("%d\n", dp[M][(1<<N)-1]); }else{ puts("-1"); } }