結果
問題 | No.137 貯金箱の焦り |
ユーザー |
![]() |
提出日時 | 2015-01-26 00:46:15 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,339 bytes |
コンパイル時間 | 740 ms |
コンパイル使用メモリ | 93,696 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-06-23 03:08:39 |
合計ジャッジ時間 | 7,687 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 TLE * 1 -- * 21 |
ソースコード
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstring> #include <cmath> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <unordered_map> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<ll, int> ll_i; typedef pair<double, int> d_i; typedef pair<ll, ll> ll_ll; typedef pair<double, double> d_d; struct edge { ll B, T, F, P; }; ll MOD = 1234567891; ll _MOD = 1000000009; double EPS = 1e-10; int INF = INT_MAX / 10; ll f(ll M, int l, int r, vector<int>& A, unordered_map<ll, ll>& mp) { ll unko = (M * 50 + l) * 50 + r; if (mp.count(unko)) return mp[unko]; if (M < 0) return 0; if (M == 0) return 1; if (l >= r) return 0; int N = A.size(); ll sum = 0; for (int m = l; m < r; m++) for (int i = 0; i < A[m]; i++) if (M / 2 - i >= 0 && M - (M / 2 - i + A[m]) >= 0) sum += (f(M / 2 - i, l, m + 1, A, mp) * f(M - (M / 2 - i + A[m]), m, r, A, mp)) % MOD; return mp[unko] = sum % MOD; } int main() { int N; ll M; cin >> N >> M; vector<int> A(N); for (int i = 0; i < N; i++) cin >> A[i]; unordered_map<ll, ll> mp; cout << f(M, 0, N, A, mp) << endl; }