Submission #61813

ソースコード

?
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) max(x,y)-min(x,y)
#define all(v) v.begin(),v.end()
#define UPDigit(a,b) (a+b-1)/b //小数点切り上げ
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7;
using namespace std;
using pii = pair<int, int>;
typedef vector<int> vit;
struct UnionFind {
//親の情報をもつ
vector<int> parent;
//親の初期化(構造体の宣言と同時に実行される)
//UnionFind a(10000); のように宣言すること
UnionFind(int size){
parent.resize(size, 0);
rep(i, size){
parent[i] = i;
}
}
//親の更新
int UpdateParent(int x){
if(parent[x] == x){
return x;
}
return parent[x] = UpdateParent(parent[x]);
}
//AとBを連結する
void ConnectParent(int a, int b){
//親の親を更新する
a = UpdateParent(parent[a]);
b = UpdateParent(parent[b]);
parent[a] = parent[b];
return;
}
//連結しているか調べる
bool same(int a, int b){
parent[a] = UpdateParent(parent[a]);
parent[b] = UpdateParent(parent[b]);
return (parent[a] == parent[b]);
}
};
/*
struct SegmentTree{
vector<lol> SumV(1000005,0);
vector<lol> MaxV(1000005,0);
vector<lol> MinV(1000005,0);
int N;
void update(int i,int x){
i += N - 1;
minv[i] = x;
maxv[i] = x;
sumv[i] = x;
while(i > 0){
i = (i - 1)/2;
maxv[i] = max(maxv[i*2+1],maxv[i*2+2]);
minv[i] = min(minv[i*2+1],minv[i*2+2]);
sumv[i] = sumv[i*2+1]+sumv[i*2+2];
}
}
void add(int i,int x){
i += N - 1;
sumv[i] += x;
maxv[i] += x;
minv[i] += x;
while(i > 0){
i = (i - 1)/2;
sumv[i] = sumv[i*2+1]+sumv[i*2+2];
minv[i] = min(minv[i*2+1],minv[i*2+2]);
maxv[i] = max(maxv[i*2+1],maxv[i*2+2]);
}
}
int getmax(int a,int b,int k,int l,int r){
if(r <= a || b <= l) return -INF;
if(a <= l && r <= b) return maxv[k];
else{
int c1 = getmax(a,b,2*k+1,l,(l+r)/2);
int c2 = getmax(a,b,2*k+2,(l+r)/2,r);
return max(c1,c2);
}
}
int getmin(int a,int b,int k,int l,int r){
if(r <= a || b <= l) return INF;
if(a <= l && r <= b) return minv[k];
else{
int c1 = getmin(a,b,2*k+1,l,(l+r)/2);
int c2 = getmin(a,b,2*k+2,(l+r)/2,r);
return min(c1,c2);
}
}
int getsum(int a,int b,int k,int l,int r){
if(r <= a || b <= l) return 0;
if(a <= l && r <= b) return sumv[k];
else{
int c1 = getsum(a,b,2*k+1,l,(l+r)/2);
int c2 = getsum(a,b,2*k+2,(l+r)/2,r);
return c1+c2;
}
}
}
*/
//最大公約数
lol gcd(lol x, lol y){
if(x < y) swap(x, y);
lol r = x % y;
while(r != 0){
x = y;
y = r;
r = x % y;
}
return y;
}
//最小公倍数
lol lcm(lol x, lol y){
lol a = x * y;
return (a / gcd(x, y));
}
signed main(void){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, x;
cin >> n >> x;
int a[n + 5];
rep(i, n){
cin >> a[i];
}
lol dp[2000] = {};
rep(i, n){
for(int j = x;j >= 0;j --){
dp[j + a[i]] += dp[j];
}
dp[a[i]] ++;
}
cout << dp[x] << '\n';
return 0;
}

ステータス

項目 データ
問題 1235 - チーム虚無新人賞おめでとう！
ユーザー名 NASSUN_ei1906
投稿日時 2020-08-07 10:48:25
言語 C++17
状態 Accepted
得点 10
ソースコード長 3670 Byte
最大実行時間 29 ms
最大メモリ使用量 748 KB

セット

セット 得点 Cases
1 R1910 1 / 1 in01.text, in02.text, in03.text, in04.text, in05.text, in06.text, in07.text, in08.text, in09.text, in10.text, in11.text, in12.text, in13.text, in14.text, in15.text, in16.text, in17.text, in18.text, in19.text, in20.text
2 R1933 9 / 9 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.text AC 23 ms 604 KB
1
2
in02.text AC 19 ms 680 KB
1
2
in03.text AC 23 ms 500 KB
1
2
in04.text AC 21 ms 572 KB
1
2
in05.text AC 24 ms 516 KB
1
2
in06.text AC 29 ms 592 KB
1
2
in07.text AC 19 ms 664 KB
1
2
in08.text AC 19 ms 608 KB
1
2
in09.text AC 24 ms 556 KB
1
2
in10.text AC 28 ms 632 KB
1
2
in11.text AC 18 ms 572 KB
1
2
in12.text AC 24 ms 644 KB
1
2
in13.text AC 20 ms 592 KB
1
2
in14.text AC 21 ms 664 KB
1
2
in15.text AC 24 ms 476 KB
1
2
in16.text AC 26 ms 552 KB
1
2
in17.text AC 22 ms 620 KB
1
2
in18.text AC 19 ms 572 KB
1
2
in19.text AC 17 ms 644 KB
1
2
in20.text AC 21 ms 592 KB
1
2
in21.text AC 24 ms 664 KB
2
in22.text AC 21 ms 608 KB
2
in23.text AC 29 ms 556 KB
2
in24.text AC 24 ms 624 KB
2
in25.text AC 22 ms 700 KB
2
in26.text AC 15 ms 648 KB
2
in27.text AC 24 ms 600 KB
2
in28.text AC 26 ms 544 KB
2
in29.text AC 29 ms 748 KB
2
in30.text AC 25 ms 564 KB
2