結果
問題 | No.1268 Fruit Rush 2 |
ユーザー |
|
提出日時 | 2020-10-23 23:40:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 592 ms / 2,000 ms |
コード長 | 788 bytes |
コンパイル時間 | 1,030 ms |
コンパイル使用メモリ | 84,344 KB |
最終ジャッジ日時 | 2025-01-15 14:17:04 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <iostream> #include <set> #include <map> using lint = long long; void solve() { int n; std::cin >> n; std::set<lint> xs, ks; while (n--) { lint x; std::cin >> x; xs.insert(x); ks.insert(x); ks.insert(x + 1); } lint ans = 0; std::map<lint, lint> dp; // sumがF_kになる選び方の総数 for (auto k : ks) { auto& pat = dp[k]; pat = 0; // F_k単体 if (xs.count(k)) ++pat; // F_{k-1}を使いF_{k-2}に帰着 if (xs.count(k - 1) && dp.count(k - 2)) pat += dp[k - 2]; ans += pat; } std::cout << ans << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }