結果
問題 | No.3046 yukicoderの過去問 |
ユーザー | mai |
提出日時 | 2019-02-22 22:31:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,574 bytes |
コンパイル時間 | 2,483 ms |
コンパイル使用メモリ | 201,868 KB |
実行使用メモリ | 18,120 KB |
最終ジャッジ日時 | 2024-11-25 09:48:44 |
合計ジャッジ時間 | 17,885 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,632 KB |
testcase_01 | AC | 2 ms
11,040 KB |
testcase_02 | AC | 2 ms
10,916 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 2 ms
11,296 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
ソースコード
//#pragma GCC optimize ("O3") //#pragma GCC target ("avx") #include "bits/stdc++.h" using namespace std; using ll = long long int; #define repeat(cnt,l) for(auto cnt=decltype(l)();(cnt)<(l);++(cnt)) #define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt)) // const int MD = 1000000007; int N, K; int X[100010]; namespace CaseGenerator { void case1() { K = 100000; N = 50000; repeat(i, N) X[i] = i * 2 + 1; } void case2() { K = 100000; N = 66666; repeat(i, 33333) X[i * 2] = i * 3 + 1, X[i * 2 + 1] = i * 3 + 2; } } void input() { cin >> K >> N; repeat(i, N) scanf("%d", X + i); } // int dp[100010]; int f[100010]; int solve() { fill(dp, dp + K + 1, 0); fill(f, f + K + 1, 0); repeat(i, N) f[X[i]] = 1; dp[0] = 1; repeat(k, K) { const int v = dp[k]; repeat(i, K - k + 1) { dp[i + k] += v * f[i]; dp[i + k] -= MD*(dp[i + k] >= MD); } } return dp[K]; } int solve_nyan(){ fill(dp, dp + K + 1, 0); dp[0] = 1; repeat(k, K){ repeat(i, N){ if (k + X[i] <= K) dp[k+X[i]] = (dp[k+X[i]] + dp[k]) % MD; } } return dp[K]; } void test(){ CaseGenerator::case1(); K = 20000; assert(solve() == solve_nyan()); CaseGenerator::case2(); K = 31415; assert(solve() == solve_nyan()); } int main() { //test(); // CaseGenerator::case1(); input(); cout << solve() << endl; //cout << solve_nyan() << endl; return 0; }