You are planning to build housing on a street. There are $n$ spots available on the street on which you can build a house. The spots are labeled from $1$ to $n$ from left to right. In each spot, you can build a house with an integer height between $0$ and $h$.
In each spot, if a house has height $a$, you can gain $a^2$ dollars from it.
The city has $m$ zoning restrictions though. The $i$-th restriction says that if the tallest house from spots $l_i$ to $r_i$ is strictly more than $x_i$, you must pay a fine of $c_i$.
You would like to build houses to maximize your profit (sum of dollars gained minus fines). Determine the maximum profit possible.
Input
The first line contains three integers $n,h,m$ ($1 \leq n,h,m \leq 50$) — the number of spots, the maximum height, and the number of restrictions, respectively.
Each of the next $m$ lines contains four integers $l_i, r_i, x_i, c_i$ ($1 \leq l_i \leq r_i \leq n$, $0 \leq x_i \leq h$, $1 \leq c_i \leq 5\,000$).
Output
Print a single integer denoting the maximum profit you can make.
Examples
input
3 3 3 1 1 1 1000 2 2 3 1000 3 3 2 1000
output
14
input
4 10 2 2 3 8 76 3 4 7 39
output
289
Note
In the first example, it’s optimal to build houses with heights $[1, 3, 2]$. We get a gain of $1^2+3^2+2^2 = 14$. We don’t violate any restrictions, so there are no fees, so the total profit is $14 – 0 = 14$.
In the second example, it’s optimal to build houses with heights $[10, 8, 8, 10]$. We get a gain of $10^2+8^2+8^2+10^2 = 328$, and we violate the second restriction for a fee of $39$, thus the total profit is $328-39 = 289$. Note that even though there isn’t a restriction on building $1$, we must still limit its height to be at most $10$.
Solution:
#include <bits/stdc++.h> using namespace std; template <typename T> class flow_graph { public: static constexpr T eps = (T) 1e-9; struct edge { int from; int to; T c; T f; }; vector<vector<int>> g; vector<edge> edges; int n; int st; int fin; T flow; flow_graph(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) { assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin); g.resize(n); flow = 0; } void clear_flow() { for (const edge &e : edges) { e.f = 0; } flow = 0; } int add(int from, int to, T forward_cap, T backward_cap) { assert(0 <= from && from < n && 0 <= to && to < n); int id = (int) edges.size(); g[from].push_back(id); edges.push_back({from, to, forward_cap, 0}); g[to].push_back(id + 1); edges.push_back({to, from, backward_cap, 0}); return id; } }; template <typename T> class dinic { public: flow_graph<T> &g; vector<int> ptr; vector<int> d; vector<int> q; dinic(flow_graph<T> &_g) : g(_g) { ptr.resize(g.n); d.resize(g.n); q.resize(g.n); } bool expath() { fill(d.begin(), d.end(), -1); q[0] = g.fin; d[g.fin] = 0; int beg = 0, end = 1; while (beg < end) { int i = q[beg++]; for (int id : g.g[i]) { const auto &e = g.edges[id]; const auto &back = g.edges[id ^ 1]; if (back.c - back.f > g.eps && d[e.to] == -1) { d[e.to] = d[i] + 1; if (e.to == g.st) { return true; } q[end++] = e.to; } } } return false; } T dfs(int v, T w) { if (v == g.fin) { return w; } int &j = ptr[v]; while (j >= 0) { int id = g.g[v][j]; const auto &e = g.edges[id]; if (e.c - e.f > g.eps && d[e.to] == d[v] - 1) { T t = dfs(e.to, min(e.c - e.f, w)); if (t > g.eps) { g.edges[id].f += t; g.edges[id ^ 1].f -= t; return t; } } j--; } return 0; } T max_flow() { while (expath()) { for (int i = 0; i < g.n; i++) { ptr[i] = (int) g.g[i].size() - 1; } T big_add = 0; while (true) { T add = dfs(g.st, numeric_limits<T>::max()); if (add <= g.eps) { break; } big_add += add; } if (big_add <= g.eps) { break; } g.flow += big_add; } return g.flow; } vector<bool> min_cut() { max_flow(); vector<bool> ret(g.n); for (int i = 0; i < g.n; i++) { ret[i] = (d[i] != -1); } return ret; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, h, m; cin >> n >> h >> m; flow_graph<int> g(n * h + m + 2, n * h + m, n * h + m + 1); int ans = 0; for (int i = 0; i < n; i++) { ans += h * h; int last = n * h + m; for (int j = 0; j < h; j++) { g.add(last, i * h + j, h * h - j * j, 0); last = i * h + j; } } const int inf = (int) 1e6; for (int i = 0; i < m; i++) { int l, r, x, c; cin >> l >> r >> x >> c; l--; r--; if (x == h) { continue; } for (int j = l; j <= r; j++) { g.add(j * h + x, n * h + i, inf, 0); } g.add(n * h + i, n * h + m + 1, c, 0); } dinic<int> d(g); ans -= d.max_flow(); cout << ans << '\n'; return 0; }