結果
問題 | No.8046 yukicoderの過去問 |
ユーザー | mai |
提出日時 | 2019-04-10 19:31:54 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,611 ms / 2,000 ms |
コード長 | 793 bytes |
コンパイル時間 | 2,345 ms |
コンパイル使用メモリ | 164,832 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 14:02:42 |
合計ジャッジ時間 | 10,702 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1,595 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 1,606 ms
5,248 KB |
testcase_06 | AC | 1,609 ms
5,248 KB |
testcase_07 | AC | 1,607 ms
5,248 KB |
testcase_08 | AC | 1,611 ms
5,248 KB |
ソースコード
#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]; void input() { cin >> K >> N; repeat(i, N) scanf("%d", X + i); } // int dp[100010]; int f[100010]; __attribute__((target("avx"))) 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 main() { input(); cout << solve() << endl; return 0; }