Fshl0

Greedy Pie Eaters

May 31st, 2021
715
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 300 + 9;
  6. const int M = N * (N + 1) / 2;
  7.  
  8. int rangeDP[N][N], maxy[N][N], mx[N][N][N], W[N], L[N], R[N];
  9.  
  10. int main () {
  11.     freopen ("pieaters.in", "r", stdin);
  12.     freopen ("pieaters.out", "w", stdout);
  13.     int n, m;
  14.     cin >> n >> m;
  15.     for (int i = 1; i <= m; i++) {
  16.         cin >> W[i] >> L[i] >> R[i];
  17.         maxy[L[i]][R[i]] = W[i];
  18.     }
  19.     for (int i = 1; i <= n; i++) {
  20.         for (int len = 1; len <= n; len++) {
  21.             for (int l = 1; l + len - 1 <= n; l++) {
  22.                 int r = l + len - 1;
  23.                 if (i > r || i < l)
  24.                     continue;
  25.                 mx[i][l][r] = max (maxy[l][r], max (mx[i][l + 1][r], mx[i][l][r - 1]));
  26.             }
  27.         }
  28.     }
  29.     for (int i = 1; i <= n; i++)
  30.         rangeDP[i][i] = mx[i][i][i];
  31.     for (int len = 2; len <= n; len++) {
  32.         for (int i = 1; i + len - 1 <= n; i++) {
  33.             int j = i + len - 1;
  34.             for (int z = i; z <= j; z++)
  35.                 rangeDP[i][j] = max (rangeDP[i][j], rangeDP[i][z - 1] + rangeDP[z + 1][j] + mx[z][i][j]);
  36.         }
  37.     }
  38.     cout << rangeDP[1][n] << "\n";
  39.     return 0;
  40. }
  41.  
RAW Paste Data