Submission #73100768

Source Code Expand

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

string N;
int K;
long long dp[105][100005][2];


long long solve(int pos, int sum, int tight) {
    
    if (sum > K) return 0;
    if (pos == N.size()) {
        return (sum == K);
    }

    // Memoization
    if (dp[pos][sum][tight] != -1)
        return dp[pos][sum][tight];

    int limit = (tight ? N[pos] - '0' : 9);

    long long ans = 0;

    for (int digit = 0; digit <= limit; digit++) {
        ans += solve(
            pos + 1,
            sum + digit,
            tight && (digit == limit)
        );
    }

    return dp[pos][sum][tight] = ans;
}

int main() {
    long long n;
    cin >> n >> K;

    N = to_string(n);

    memset(dp, -1, sizeof(dp));

    cout << solve(0, 0, 1);

    return 0;
}

Submission Info

Submission Time
Task B - Digit Sum
User praveen9kk
Language C++23 (GCC 15.2.0)
Score 200
Code Size 809 Byte
Status AC
Exec Time 77 ms
Memory 167736 KiB

Compile Error

./Main.cpp: In function 'long long int solve(int, int, int)':
./Main.cpp:12:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (pos == N.size()) {
      |         ~~~~^~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 200 / 200
Status
AC × 3
AC × 12
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All 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
Case Name Status Exec Time Memory
random_01.txt AC 77 ms 167676 KiB
random_02.txt AC 77 ms 167708 KiB
random_03.txt AC 77 ms 167548 KiB
random_04.txt AC 76 ms 167708 KiB
random_05.txt AC 77 ms 167688 KiB
random_06.txt AC 77 ms 167736 KiB
random_07.txt AC 77 ms 167520 KiB
random_08.txt AC 77 ms 167684 KiB
random_09.txt AC 77 ms 167684 KiB
sample_01.txt AC 77 ms 167524 KiB
sample_02.txt AC 77 ms 167496 KiB
sample_03.txt AC 77 ms 167700 KiB