Many Requirements [AtCoder Beginner Contest 165 C]

https://atcoder.jp/contests/abc165/tasks/abc165_c

解説

https://atcoder.jp/contests/abc165/submissions/12649721

メタ読みをする。
制約を見ると、数列Aの全探索ができそうな感じ。
dfsを使って数列を全探索していこう。
dfsを使った数列の全探索方法が分からない場合は、そちらを先に学ぶといいかもしれない。
重複順列 dfs - Google 検索
重複順列として考えると、10¹⁰で間に合わないが、広義単調増加である制約があるので、前の要素以下を列挙しないようにすると大丈夫。
このように全探索をするが、必要ない部分についての遷移を削減することを枝刈りと良い、枝刈り全探索というテクもある。

あとは、広義単調増加である数列Aすべてに対してスコアを計算して最大値を求めると答え。

int N, M, Q, a[50], b[50], c[50], d[50];
//---------------------------------------------------------------------------------------------------
int ans = 0;
int A[10];
void dfs(int cu = 0, int lst = 1) {
    if (cu == N) {
        int tot = 0;
        rep(i, 0, Q) if (A[b[i]] - A[a[i]] == c[i]) tot += d[i];
        chmax(ans, tot);
        return;
    }

    rep(nxt, lst, M + 1) {
        A[cu] = nxt;
        dfs(cu + 1, nxt);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, Q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--; b[i]--;
    }

    dfs();
    cout << ans << endl;
}