結果
問題 | No.3046 yukicoderの過去問 |
ユーザー | mai |
提出日時 | 2019-04-10 19:31:54 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,475 ms / 2,000 ms |
コード長 | 793 bytes |
コンパイル時間 | 2,037 ms |
コンパイル使用メモリ | 133,084 KB |
実行使用メモリ | 4,744 KB |
最終ジャッジ日時 | 2023-08-20 12:20:39 |
合計ジャッジ時間 | 9,879 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1,475 ms
4,468 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 1,441 ms
4,376 KB |
testcase_06 | AC | 1,453 ms
4,744 KB |
testcase_07 | AC | 1,457 ms
4,556 KB |
testcase_08 | AC | 1,465 ms
4,744 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; }