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
Task C - Tak and Cards
User kazunetakahashi
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1031 Byte
Status AC
Exec Time 115 ms
Memory 70784 KB

Judge Result

Set Name Sample Subtask1 All
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
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.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