SRM 768 Div21000

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

#define pb push_back

typedef long long ll;
typedef vector<ll> vll;
const ll mod = 1e9 + 7;

struct MeanMedianCount {
    int n, mean, median;
    ll solve(vector<vector<vll> >& dp, int i, int s, int p) {
        if (i == n + 1) {
            if (s < (mean * n)) return 0;
            if (p <= n / 2) return 0;
            return 1;
        }
        if (dp[i][s][p] != -1)
            return dp[i][s][p];
        ll ans = 0;
        for (int gr = 0; gr <= 10; ++gr) {
            ans += solve(dp, i + 1, s + gr, p + (gr >= median));
            ans %= mod;
        }
        return dp[i][s][p] = ans;
    }
    int getCount(int N, int needMean, int needMedian) {
        n = N;
        mean = needMean;
        median = needMedian;
        vector<vector<vll> > dp(n + 2, vector<vll>(10 * (n + 2), vll((n + 2), -1)));
        return solve(dp, 1, 0, 0);
    }
};

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    MeanMedianCount mc;
    cout << mc.getCount(5, 10, 8) << "\n";
}