結果
問題 |
No.115 遠足のおやつ
|
ユーザー |
![]() |
提出日時 | 2015-05-08 23:47:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,161 bytes |
コンパイル時間 | 548 ms |
コンパイル使用メモリ | 63,352 KB |
実行使用メモリ | 9,892 KB |
最終ジャッジ日時 | 2024-11-21 18:58:37 |
合計ジャッジ時間 | 8,101 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 TLE * 1 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> using namespace std; int n; bool availables[101]; int picked[10]; bool solve(int d, int k) { if (k == 0) { return (d == 0); // only if total price equals 0 yen } int maxPricePickingUpK = 0; int pickedCount = 0; for (int i = n; i >= 1 && pickedCount < k; --i) { if (availables[i]) { maxPricePickingUpK += i; ++pickedCount; } } if (d > maxPricePickingUpK) { return false; } bool plausible = false; for (int i = 1; i <= n; ++i) { if (availables[i]) { availables[i] = false; picked[k - 1] = i; plausible |= solve(d - i, k - 1); availables[i] = true; if (plausible) { break; } } } return plausible; } int main() { int d, k; cin >> n; // sweets cin >> d; // total yen cin >> k; // count fill(&availables[1], &availables[n] + 1, true); if (n < k) { cout << -1 << endl; return 0; } bool solved = solve(d, k); if (solved) { vector<int> v(&picked[0], &picked[k - 1] + 1); for (int i = k - 1; i >= 0; --i) { if (i != k - 1) { cout << " "; } cout << picked[i]; } cout << endl; } else { cout << -1 << endl; } return 0; }