Contest Duration: - (local time) (100 minutes) Back to Home

Submission #855770

Source Code Expand

Copy
```#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <tuple>
#include <cmath>
#include <cassert>
#include <string>

using namespace std;

typedef long long ll;

int N, A;
int x[100010];

ll memo[60][60][2510];

ll f(int n, int m, int a) {
if (memo[n][m][a] != -1) return memo[n][m][a];
ll ans = -1;
if (m == 0 && a == 0) {
ans = 1;
} else if (m == 0) {
ans = 0;
} else if (n < m) {
ans = 0;
} else if (a-x[n-1] < 0) {
ans = f(n-1, m, a);
} else {
ans = f(n-1, m-1, a-x[n-1]) + f(n-1, m, a);
}
// cerr << "memo[" << n << "][" << m << "][" << a << "] = " << ans << endl;
return memo[n][m][a] = ans;
}

int main() {
cin >> N >> A;
for (auto i = 0; i < N; i++) {
cin >> x[i];
}
fill(&memo[0][0][0], &memo[0][0][0]+60*60*2510, -1);
ll ans = 0;
for (auto i = 1; i <= N; i++) {
ans += f(N, i, A*i);
}
cout << ans << endl;
}
```

#### Submission Info

Submission Time 2016-08-28 21:32:50+0900 C - Tak and Cards kazunetakahashi C++14 (GCC 5.4.1) 300 1031 Byte AC 115 ms 70784 KB

#### Judge Result

Score / Max Score 0 / 0 200 / 200 100 / 100
Status
 AC × 4
 AC × 12
 AC × 24
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Case Name Status Exec Time Memory
example_01.txt AC 100 ms 70784 KB
example_02.txt AC 101 ms 70784 KB
example_03.txt AC 100 ms 70784 KB
example_04.txt AC 101 ms 70784 KB
subtask1_01.txt AC 101 ms 70784 KB
subtask1_02.txt AC 115 ms 70784 KB
subtask1_03.txt AC 115 ms 70784 KB
subtask1_04.txt AC 101 ms 70784 KB
subtask1_05.txt AC 101 ms 70784 KB
subtask1_06.txt AC 114 ms 70784 KB
subtask1_07.txt AC 115 ms 70784 KB
subtask1_08.txt AC 101 ms 70784 KB
subtask1_09.txt AC 115 ms 70784 KB
subtask2_01.txt AC 107 ms 70784 KB
subtask2_02.txt AC 109 ms 70784 KB
subtask2_03.txt AC 106 ms 70784 KB
subtask2_04.txt AC 100 ms 70784 KB
subtask2_05.txt AC 101 ms 70784 KB
subtask2_06.txt AC 102 ms 70784 KB
subtask2_07.txt AC 104 ms 70784 KB
subtask2_08.txt AC 104 ms 70784 KB
subtask2_09.txt AC 104 ms 70784 KB
subtask2_10.txt AC 103 ms 70784 KB
subtask2_11.txt AC 105 ms 70784 KB