Submission #17992965

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, X;
vector<ll> A(60, 0);
const ll M = 100000;
ll memo[60][M] = {};

ll cnt(ll index, ll zan) {
  if (zan < M && memo[index][zan] > 0) return memo[index][zan];
  if (index == 0) return 1;
  if (zan == 0) return 1;
  ll temp = zan / A[index];
  ll zan1 = zan - A[index] * temp;
  ll zan2 = abs(zan - A[index] * (temp + 1));

  ll ans;
  if (temp == 0 && index != N - 1) ans = cnt(index - 1, zan1);
  else if (zan1 == 0) ans = cnt(index - 1, zan2);
  else if (zan2 == 0) ans = cnt(index - 1, zan1);
  else ans = cnt(index - 1, zan1) + cnt(index - 1, zan2);
  if (zan < M) memo[index][zan] = ans;
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> N;
  cin >> X;
  for (ll i = 0; i < N; i++) {
    cin >> A[i];
  }
  ll ans = cnt(N - 1, X);
  cout << ans << '\n';
  return 0;
}

Submission Info

Submission Time
Task F - Valid payments
User nakaken88
Language C++ (GCC 9.2.1)
Score 600
Code Size 919 Byte
Status AC
Exec Time 48 ms
Memory 3868 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 4
AC × 35
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All answer_big_00.txt, border_00.txt, border_01.txt, border_02.txt, border_03.txt, border_04.txt, border_05.txt, border_06.txt, border_07.txt, border_08.txt, border_09.txt, handmade_00.txt, handmade_01.txt, handmade_02.txt, handmade_03.txt, longest_00.txt, longest_01.txt, longest_02.txt, longest_03.txt, longest_04.txt, overflow_killer_00.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
answer_big_00.txt AC 48 ms 3680 KiB
border_00.txt AC 3 ms 3640 KiB
border_01.txt AC 2 ms 3548 KiB
border_02.txt AC 2 ms 3512 KiB
border_03.txt AC 3 ms 3552 KiB
border_04.txt AC 3 ms 3640 KiB
border_05.txt AC 2 ms 3600 KiB
border_06.txt AC 2 ms 3568 KiB
border_07.txt AC 2 ms 3584 KiB
border_08.txt AC 2 ms 3540 KiB
border_09.txt AC 4 ms 3564 KiB
handmade_00.txt AC 1 ms 3636 KiB
handmade_01.txt AC 2 ms 3552 KiB
handmade_02.txt AC 3 ms 3644 KiB
handmade_03.txt AC 2 ms 3600 KiB
longest_00.txt AC 3 ms 3868 KiB
longest_01.txt AC 2 ms 3744 KiB
longest_02.txt AC 37 ms 3628 KiB
longest_03.txt AC 6 ms 3568 KiB
longest_04.txt AC 8 ms 3608 KiB
overflow_killer_00.txt AC 2 ms 3468 KiB
random_00.txt AC 2 ms 3584 KiB
random_01.txt AC 3 ms 3488 KiB
random_02.txt AC 5 ms 3600 KiB
random_03.txt AC 2 ms 3520 KiB
random_04.txt AC 2 ms 3616 KiB
random_05.txt AC 2 ms 3552 KiB
random_06.txt AC 2 ms 3492 KiB
random_07.txt AC 2 ms 3556 KiB
random_08.txt AC 3 ms 3720 KiB
random_09.txt AC 2 ms 3472 KiB
sample_01.txt AC 2 ms 3564 KiB
sample_02.txt AC 3 ms 3612 KiB
sample_03.txt AC 1 ms 3532 KiB
sample_04.txt AC 2 ms 3668 KiB