注意到每个权值只计算一次，考虑最大权闭合子图。
每种代号新建一个点，权值为代号的平方乘m。
每种寿司的权值为它本身的代号，向他代号对应的点连边。
每个区间新建一个点，权值是他的代价，同时向这个区间的子区间和这个区间内的所有寿司连边。
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 15010;
const int_t SOURCE = 15001;
const int_t SINK = 15002;
const int_t OFFSET = 10000;
const int_t OFFSET2 = 14000;
const int_t INF = 0x7fffffff;
struct Edge {
int_t to, capacity, flow;
Edge* rev;
};
std::vector<Edge*> graph[LARGE + 1];
int_t dis[LARGE + 1], curr[LARGE + 1];
bool visited[LARGE + 1];
void pushEdge(int_t from, int_t to, int_t capacity) {
Edge* edge0 = new Edge{to, capacity, 0};
Edge* edge1 = new Edge{from, 0, 0, edge0};
edge0->rev = edge1;
graph[from].push_back(edge0);
graph[to].push_back(edge1);
#ifdef DEBUG
cout << "Edge " << from << "," << to << "," << capacity << endl;
#endif
}
bool BFS(int_t source, int_t sink) {
std::fill(dis + 1, dis + 1 + LARGE, INF);
std::fill(curr + 1, curr + 1 + LARGE, 0);
std::fill(visited + 1, visited + 1 + LARGE, false);
std::queue<int_t> queue;
queue.push(source);
dis[source] = 0;
visited[source] = true;
while (queue.empty() == false) {
int_t front = queue.front();
queue.pop();
for (Edge* edge : graph[front]) {
if (edge->capacity > edge->flow && visited[edge->to] == false) {
dis[edge->to] = dis[front] + 1;
visited[edge->to] = true;
queue.push(edge->to);
}
}
}
return visited[sink];
}
int_t DFS(int_t vtx, int_t sink, int_t minf = INF) {
if (minf == 0 || vtx == sink) return minf;
int_t result = 0;
for (int_t& i = curr[vtx]; i < graph[vtx].size(); i++) {
Edge* edge = graph[vtx][i];
if (dis[edge->to] == dis[vtx] + 1) {
int_t x = DFS(edge->to, sink,
std::min(minf, edge->capacity - edge->flow));
if (x > 0) {
minf -= x;
result += x;
edge->flow += x;
edge->rev->flow -= x;
if (minf == 0) break;
}
}
}
return result;
}
int main() {
int_t n, m;
cin >> n >> m;
int_t result = 0;
std::set<int_t> numbers;
for (int_t i = 1; i <= n; i++) {
int_t x;
cin >> x;
numbers.insert(x);
pushEdge(OFFSET2 + i, SINK, x);
pushEdge(OFFSET2 + i, OFFSET + x, INF);
// result += x;
}
for (int_t x : numbers) {
// result += x * x * m;
pushEdge(OFFSET + x, SINK, x * x * m);
}
const auto encode = [&](int_t r, int_t c) -> int_t {
return (r - 1) * n + c;
};
for (int_t i = 1; i <= n; i++) {
for (int_t j = i; j <= n; j++) {
int_t x;
cin >> x;
if (x > 0) {
result += x;
pushEdge(SOURCE, encode(i, j), x);
} else {
pushEdge(encode(i, j), SINK, -x);
}
if (i != j) {
pushEdge(encode(i, j), encode(i + 1, j), INF);
pushEdge(encode(i, j), encode(i, j - 1), INF);
}
for (int_t k = i; k <= j; k++) {
pushEdge(encode(i, j), OFFSET2 + k, INF);
}
}
}
while (BFS(SOURCE, SINK)) {
int_t x = DFS(SOURCE, SINK);
#ifdef DEBUG
cout << "flow " << x << endl;
#endif
result -= x;
}
cout << result << endl;
return 0;
}