题目大意

有 $n$ 个人做报告，第 $i$ 个人会使兴奋度 $x$ 变成 $a_i\lvert x\rvert+b_ix+c_i$ 。

初始兴奋度为 $s$ ，调整报告顺序使得最后的兴奋度最大。

$n,s,|a_i|,|b_i|,|c_i|\le15$ .

思路

调整顺序，范围又很小，于是考虑状压 DP。

贡献是分段函数，可以看作是端点在 $y$ 轴上的两条射线，并不是 $x$ 值越大，函数值越大。

转移时对新函数的两条线分类讨论，斜率大于零我们希望他越大，反之亦然，则为了得到新状态的最大值，需要分别维护原有状态在 $y$ 轴两侧的（离 $y$ 轴的）最近最远值。而要维护这四值，又需要维护更多值。然而注意到数据范围很小，直接记录值域 $|V|\le15\times15$ 所有值的可达性即可。

启示：不要陷入复杂的零点、极值的讨论。

时间复杂度 $\mathcal{O}(2^nn^2|c|)$ 。

代码

#include <bits/stdc++.h>
#define ll long long
#define LL __int128

using namespace std;

const int N = 15, V = 250, mod = 998244353;
const int aV = 500;
const LL inf = 1e36;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

inline int add (int a, int b) { return a + b > mod? a + b - mod: a + b; }
inline int dec (int a, int b) { return a < b? a - b + mod: a - b; }
inline int mul (int a, int b) { return 1ll * a * b % mod; }

void write(LL x) {
	if (x < 0) putchar('-'), x = -x;
	if (x >= 10) write(x / 10);
	putchar('0' + x % 10);
}

namespace Main {
	int n, s;
	int a[N], b[N], c[N];

	struct state {
		LL maxp, minp, maxn, minn;
		bool vis[aV + 10];
		state() {
			for (int i = 0; i < aV; ++i) vis[i] = 0;
			minn = maxp = 0; maxn = -inf, minp = inf;
		}	
		void update(LL x) {
			if (-V <= x && x <= V) vis[x + V] = 1;
			if (x > 0) maxp = max(maxp, x), minp = min(minp, x);
			else maxn = max(maxn, x), minn = min(minn, x);
		}
	} f[1 << N];

	LL abs(LL x) { return x < 0? -x: x; }
	LL val(LL x, int i) { return abs(x) * a[i] + x * b[i] + c[i];}

	int main () {
		n = read(), s = read();
		for (int i = 0; i < n; ++i) a[i] = read(), b[i] = read(), c[i] = read();
		f[0].update(s);
		for (int S = 0; S < (1 << n); ++S) {
			for (int i = 0; i < n; ++i) {
				if (S >> i & 1) continue;
				int nS = S | (1 << i);
				for (int v = -V; v <= V; ++v) {
					if (!f[S].vis[v + V]) continue;
					f[nS].update(val(v, i));
				}
				if (f[S].minp <= f[S].maxp) f[nS].update(val(f[S].minp, i)), f[nS].update(val(f[S].maxp, i));
				if (f[S].minn <= f[S].maxn) f[nS].update(val(f[S].minn, i)), f[nS].update(val(f[S].maxn, i));
			}
		}
		int S = (1 << n) - 1;
		LL ans = -inf;
		for (int v = V; v >= -V; --v) if (f[S].vis[v + V]) ans = max(ans, (LL) v);
		if (f[S].minp <= f[S].maxp) ans = max(ans, f[S].maxp);
		if (f[S].minn <= f[S].maxn) ans = max(ans, f[S].maxn);
		write(ans); putchar(10);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}