Greedy Pie Eaters

#include <bits/stdc++.h>

using namespace std;

const int N = 300 + 9;
const int M = N * (N + 1) / 2;

int rangeDP[N][N], maxy[N][N], mx[N][N][N], W[N], L[N], R[N];

int main () {
    freopen ("pieaters.in", "r", stdin);
    freopen ("pieaters.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> W[i] >> L[i] >> R[i];
        maxy[L[i]][R[i]] = W[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int len = 1; len <= n; len++) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                if (i > r || i < l)
                    continue;
                mx[i][l][r] = max (maxy[l][r], max (mx[i][l + 1][r], mx[i][l][r - 1]));
            }
        }
    }
    for (int i = 1; i <= n; i++)
        rangeDP[i][i] = mx[i][i][i];
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int z = i; z <= j; z++)
                rangeDP[i][j] = max (rangeDP[i][j], rangeDP[i][z - 1] + rangeDP[z + 1][j] + mx[z][i][j]);
        }
    }
    cout << rangeDP[1][n] << "\n";
    return 0;
}