Submission #69074

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* #region header */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0;i < (int)(n);++i)
#define MS(x) memset((x), -1, sizeof((x)))
#define ALL(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
bool is_npos(string::size_type x) { return x == string::npos; }
using PI = pair<int, int>;
template <class T>ostream &operator<<(ostream &os, const vector<T>&v){
if(v.size() > 0){
os << v[0];
for(int i = 1;i < v.size();i++) os << " " << v[i];
}
return os;
}
/* #endregion */
#define MOD 998244353
template<int64_t mod> struct Modint{
int64_t val;
Modint(): val(0) {}
Modint(int64_t x) : val(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
Modint inv(){
return pow(mod-2);
}
Modint &operator+=(const Modint &x){
if((val += x.val) >= mod) val -= mod;
return *this;
}
Modint &operator-=(const Modint &x){
if((val -= x.val) < 0) val += mod;
return *this;
}
Modint &operator*=(const Modint &x){
val = (val * x.val) % mod;
return *this;
}
Modint &operator/=(const Modint &x){
val = (val * x.inv().val) % mod;
return *this;
}
Modint operator-() const noexcept{ return Modint(-val); }
Modint operator+(const Modint &x) const noexcept{ return Modint(*this) += x; }
Modint operator-(const Modint &x) const noexcept{ return Modint(*this) -= x; }
Modint operator*(const Modint &x) const noexcept{ return Modint(*this) *= x; }
Modint operator/(const Modint &x) const noexcept{ return Modint(*this) /= x; }
Modint operator+(const int &x) const noexcept{ return Modint(*this) += x; }
Modint operator-(const int &x) const noexcept{ return Modint(*this) -= x; }
Modint operator*(const int &x) const noexcept{ return Modint(*this) *= x; }
Modint operator/(const int &x) const noexcept{ return Modint(*this) /= x; }
Modint operator++(int) { if((++val)==mod) val = 0; return *this; }
Modint operator--(int) { if((++val)==mod) val = 0; return *this; }
friend ostream& operator<<(ostream &os, Modint x) noexcept { os << x.val; return os; }
friend istream& operator>>(istream &is, Modint &x) noexcept {
int64_t t; is >> t;
x = Modint<mod>(t);
return is;
}
Modint pow_e(int64_t n){
Modint mul(val);
Modint vtmp(1);
while(n > 0){
if(n & 1) vtmp *= mul;
mul *= mul;
n >>= 1;
}
return (*this = vtmp);
}
Modint pow(int64_t n) { return Modint(*this).pow_e(n); }
static int64_t get_mod() { return mod; }
operator int() const { return (int)val; }
};
using mint = Modint<MOD>;
int n;
int a[210];
int memo[210][2][40010];
mint dp(int i, int sum){
if(i == n){
return sum == 0;
}
if(~memo[i][sum >= 0][abs(sum)]) return memo[i][sum >= 0][abs(sum)];
mint ans = dp(i+1, sum+a[i]) + dp(i+1, sum-a[i]);
return memo[i][sum >= 0][abs(sum)] = ans;
}
int main(){
cin >> n;
rep(i, n){
cin >> a[i];
}
MS(memo);
cout << dp(0, 0) << endl;
return 0;
}

ステータス

項目 データ
問題 1529 - Red Black Balls
ユーザー名 ei1719
投稿日時 2021-12-05 23:42:43
言語 C++14
状態 Accepted
得点 3
ソースコード長 3153 Byte
最大実行時間 74 ms
最大メモリ使用量 66488 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 50 ms 66268 KB
1
in02.txt AC 28 ms 66132 KB
1
in03.txt AC 28 ms 66132 KB
1
in04.txt AC 31 ms 66132 KB
1
in05.txt AC 32 ms 66128 KB
1
in06.txt AC 32 ms 66252 KB
1
in07.txt AC 41 ms 66248 KB
1
in08.txt AC 29 ms 66116 KB
1
in09.txt AC 40 ms 66244 KB
1
in10.txt AC 52 ms 66240 KB
1
in11.txt AC 31 ms 66108 KB
1
in12.txt AC 38 ms 66100 KB
1
in13.txt AC 51 ms 66096 KB
1
in14.txt AC 34 ms 66216 KB
1
in15.txt AC 46 ms 66208 KB
1
in16.txt AC 47 ms 66204 KB
1
in17.txt AC 37 ms 66196 KB
1
in18.txt AC 29 ms 66192 KB
1
in19.txt AC 49 ms 66188 KB
1
in20.txt AC 48 ms 66184 KB
1
in21.txt AC 30 ms 66304 KB
1
in22.txt AC 41 ms 66420 KB
1
in23.txt AC 29 ms 66284 KB
1
in24.txt AC 43 ms 66400 KB
1
in25.txt AC 34 ms 66396 KB
1
in26.txt AC 67 ms 66392 KB
1
in27.txt AC 69 ms 66384 KB
1
in28.txt AC 74 ms 66372 KB
1
in29.txt AC 30 ms 66368 KB
1
in30.txt AC 47 ms 66236 KB
1
in31.txt AC 60 ms 66360 KB
1
in32.txt AC 30 ms 66488 KB
1
in33.txt AC 30 ms 66480 KB
1
in34.txt AC 53 ms 66476 KB
1
in35.txt AC 56 ms 66464 KB
1
in36.txt AC 57 ms 66464 KB
1
in37.txt AC 32 ms 66456 KB
1
in38.txt AC 34 ms 66452 KB
1
in39.txt AC 31 ms 66448 KB
1
in40.txt AC 32 ms 66440 KB
1
sample01.txt AC 37 ms 66440 KB
1
sample02.txt AC 32 ms 66432 KB
1