21742022-12-28 22:47:14TuruTamasBürokrácia (40)cpp11Wrong answer 0/40400ms4016 KiB
#include <bits/stdc++.h>
using namespace std;

int sumTo(long int x) {
    long int r = 0;
    for (long int i = 1; i <= x; i++)
    {
        r += i;
    }
    return r;
}

long int recurse(int a, int b) {
    // if (cache[a][b] != -1) {
    //     return cache[a][b];
    // }
    // cout << a << ' ' << b << ":\n";
    if (a == 2) {
        if (b % 2 == 0) {
            return b/2 - 1;
        }
        else {
            return b/2;
        }
    }
    long int r = 0;
    for (long int i = 1; i < b/2; i++)
    {   
        if ((i + i + a)/2 * a > b) {
            break;
        }
        // cout << "into: ";
        r += recurse(a - 1, b - i) - i;
    }
    // cache[a][b] = r;
    // cout << a << ' ' << b << " return: " << r << '\n';
    return r;
}

int main() {
    int N;
    cin >> N;
    int a = 0;
    cin.tie(0);
    iostream::sync_with_stdio(0);
    for (int i = 0; i < N; i++)
    {
        if (sumTo(i) > N) {
            a = i - 1;
            break;
        }
    }
    // // array<array<int, 200>, 20> cache;
    // for (int i = 0; i < 20; i++)
    // {
    //     cache[i].fill(-1);
    // }
    int s = 1;
    for (int i = 2; i <= a; i++)
    {
        int g = recurse(i, N);
        cout << i << ' ' << g << '\n';
        s += g;
    }
    // cout << recurse(4, 20);
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base0/40
1Wrong answer0/03ms1896 KiB
2Wrong answer0/12ms2120 KiB
3Time limit exceeded0/1347ms1696 KiB
4Time limit exceeded0/1372ms2532 KiB
5Time limit exceeded0/1384ms1792 KiB
6Time limit exceeded0/1337ms2772 KiB
7Time limit exceeded0/1368ms2848 KiB
8Time limit exceeded0/2384ms2828 KiB
9Time limit exceeded0/2356ms2832 KiB
10Time limit exceeded0/2375ms2996 KiB
11Time limit exceeded0/2365ms3192 KiB
12Time limit exceeded0/2358ms3388 KiB
13Time limit exceeded0/2344ms3464 KiB
14Time limit exceeded0/2356ms3460 KiB
15Time limit exceeded0/2354ms2916 KiB
16Time limit exceeded0/2374ms3896 KiB
17Time limit exceeded0/2344ms3908 KiB
18Time limit exceeded0/2372ms3092 KiB
19Time limit exceeded0/2372ms2984 KiB
20Time limit exceeded0/2368ms3968 KiB
21Time limit exceeded0/2345ms3188 KiB
22Time limit exceeded0/2374ms4016 KiB
23Time limit exceeded0/4400ms3868 KiB