题解

样例 1 的第一步就很有用。初始能量是 $3$，选 A 后还剩 $1$，这一步没有把能量用成负数，但下一项要求至少有 $5$，后面已经走不下去了。

所以，决定一个位置能不能填 A，要看选完以后能否完成整个后缀。只要后面还有解，我们就应该填 A，因为答案要求字典序最小，当前位置的 A 比后面怎样选择都更优先。

本题还允许能量增加量为负。判断一段方案是否合法时，要同时检查开始第 $i$ 项前的能量不少于 $h_i$，以及完成这一项后的能量非负。

先把小数据做出来

当 $n\le18$ 时，可以按顺序搜索每项的选择。搜索到第 $i$ 项时，先检查启动能量，再依次尝试 A、B，选择后若能量为负就停止这条分支。第一次找到能完成全部检修的方案，就可以直接输出。

搜索时先走 A 分支，枚举到的完整字符串就是字典序从小到大的顺序。非法前缀无论怎样补全都不会合法，剪去它们不影响答案，所以第一个找到的完整方案一定是所求答案。若搜索结束仍没有找到方案，就输出 $-1$。

递归中保存当前能量，每次转移只用常数时间。搜索树的结点数不超过 $1+2+\cdots+2^n$，时间复杂度为 $O(2^n)$，加上存储输入、递归栈和答案，空间复杂度为 $O(n)$。子任务 1 可以这样拿到 $15$ 分。

用一次模拟判断后面有没有解

先暂时放下字典序，只判断从某一项、某个能量开始，能不能完成剩下的检修。

这时每一步都选能量增加量较大的方案就行。记

$$m_i=\max(a_i,b_i).$$

从同样的初始能量出发，按这个方法走到任意一项前，能量都不会小于其他方案。因为每一步加上的数都尽可能大，两种方案之间已经积累的能量差也不会消失。题目只要求能量达到下限，且没有容量上限，能量更多不会让后续选择变差。

于是，如果这个方法在某项无法启动，或完成后能量变成负数，其他方案也一定过不去；如果它顺利走完，就已经找到了一种可行方案。这样一次 $O(n)$ 的模拟，就能准确判断后缀是否有解。

现在回来构造答案。先对整个序列做一次可行性检查，无解就输出 $-1$。否则从左往右枚举位置，尝试选 A，并从选 A 后的能量出发检查剩下的后缀。检查成功就留下 A；失败就选 B。

这里选 B 不需要再试一遍。进入这一项时，我们已经保证当前前缀能补成完整方案；A 不能补全，那么剩下的 B 必然可以。这样每一步都保留了完成后缀的可能性，又在可行的选择中优先用了 A。假如存在字典序更小的答案，在两者第一个不同的位置，它一定用了 A、我们用了 B，但我们只有确认 A 无法补全时才会用 B，矛盾。

至多做 $n$ 次后缀模拟，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。$n\le2000$ 时足够，可以通过子任务 1、2，共 $35$ 分。

两个特殊性质

子任务 3 保证 $a_i\ge b_i$。此时 A 既让字典序更小，又留下不少于 B 的能量，整段都选 A 就能得到最多的能量。直接模拟全 A 的方案，它若合法就是答案；若它在中途失败，其他方案也不可能成功。

这个做法时间复杂度为 $O(n)$，读入时就能模拟，除输出字符串外只用 $O(1)$ 额外空间，可以得到子任务 3 的 $10$ 分。和前面的小数据做法按条件分支，已经能拿到 $45$ 分。

子任务 4 中 $h_i=0$，而且两种方案都只会消耗能量。设第 $i$ 项至少要消耗

$$c_i=\min(-a_i,-b_i)=-\max(a_i,b_i),$$

再设 $s_i=c_i+c_{i+1}+\cdots+c_n$，并令 $s_{n+1}=0$。从第 $i$ 项开始，能量至少要有 $s_i$ 才能完成后缀，因为每项的消耗不可能少于 $c_i$。能量达到这个数也就足够了，逐项选择消耗较少的方案，总消耗恰好为 $s_i$；过程中消耗只会累积，能量不会提前变成负数。

先算出后缀和。如果 $E<s_1$，直接输出 $-1$。否则从左往右，当前能量记为 $e$，只要 $e+a_i\ge s_{i+1}$ 就选 A，否则选 B。这里仍然是在判断 A 能否保留一个可行后缀，字典序最小的理由和前面相同。

预处理和构造都是 $O(n)$ 时间，空间复杂度为 $O(n)$，可以得到子任务 4 的 $20$ 分。把这两个性质分支和 $O(n^2)$ 做法组合起来，可以通过子任务 1 至 4，共 $65$ 分。

把后缀的最低需求算出来

子任务 4 的后缀和已经给出了一个方向。一般情况中，能量可能增加，中途还有启动门槛，后缀需求不能直接求和，但仍然可以用一个数表示。

设 $need_i$ 表示开始第 $i$ 项之前，能够完成第 $i$ 到第 $n$ 项所需的最低能量。我们希望得到一个准确的判断条件，即当前能量为 $e$ 时，后缀有解当且仅当 $e\ge need_i$。

完成全部检修后，能量只需非负，所以边界是 $need_{n+1}=0$。假设已经算出 $need_{i+1}$，现在考虑第 $i$ 项。

开始时必须有 $e\ge h_i$。选完这一项后，还得达到下一个后缀的需求。只判断有没有解时，可以选择增加量较大的方案，所以还要满足

$$e+\max(a_i,b_i)\ge need_{i+1}.$$

把右边需要的能量倒推回来，就是 $e\ge need_{i+1}-\max(a_i,b_i)$。两个条件都要成立，最低能量取二者的较大值，得到

$$need_i=\max\bigl(h_i,\ need_{i+1}-\max(a_i,b_i)\bigr).$$

这个式子给出的条件既必要，也足够。任何可行方案都得通过当前启动门槛，且它这一项的增加量不超过 $\max(a_i,b_i)$，所以不能低于式子算出的需求。反过来，能量只要达到 $need_i$，就能启动这一项；选增加量较大的方案后，能量又能达到 $need_{i+1}$，接下来便能完成后缀。

从 $need_{n+1}=0$ 开始倒序应用这段推理，就证明了全部 $need_i$ 的含义。由于 $h_i\ge0$，这些需求也都非负，转移同时包含了每项完成后能量不能为负的要求。

算出数组以后，如果 $E<need_1$，无解。否则正序构造答案，第 $i$ 项优先选 A 的条件就是

$$e+a_i\ge need_{i+1}.$$

满足时选 A，不满足时选 B，并更新能量。开始处理第 $i$ 项时始终有 $e\ge need_i$，所以当前启动门槛已经满足；A 不可行时，B 必然可行，选完后仍有 $e\ge need_{i+1}$。这一不变量保证了输出方案合法。每一位又都选择了仍能完成后缀的最小字符，因此答案的字典序最小。

按样例 1 计算，可以得到 $need_4=0$、$need_3=3$、$need_2=5$、$need_1=3$。第一项选 A 后只剩 $1<need_2$，只能选 B，能量变为 $5$；第二项选 A 后剩 $4\ge need_3$；第三项选 A 后剩 $0=need_4$，得到 BAA。恰好等于需求时也可行，判断一定要允许等号。

倒序计算一次、正序构造一次，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，可以通过全部子任务，得到 $100$ 分。

能量和后缀需求都要用 64 位整数。虽然输入的单个数绝对值不超过 $10^9$，累计量却可能达到 $n\times10^9$ 的数量级，32 位整数会溢出。下面代码用从 $0$ 开始的下标，数组中的 $need[n]=0$ 对应上文的 $need_{n+1}=0$。

参考代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll energy;
    cin >> n >> energy;
    vector<ll> h(n), a(n), b(n), need(n + 1, 0);
    for (int i = 0; i < n; ++i) cin >> h[i] >> a[i] >> b[i];

    // need[i] 是开始第 i 项前，为完成整个后缀所需的最低能量。
    for (int i = n - 1; i >= 0; --i) {
        need[i] = max(h[i], need[i + 1] - max(a[i], b[i]));
    }
    if (energy < need[0]) {
        cout << -1 << '\n';
        return 0;
    }

    string answer;
    answer.reserve(n);
    for (int i = 0; i < n; ++i) {
        // 只要选 A 以后还能完成后缀，就优先选 A。
        if (energy + a[i] >= need[i + 1]) {
            answer += 'A';
            energy += a[i];
        } else {
            answer += 'B';
            energy += b[i];
        }
    }
    cout << answer << '\n';
    return 0;
}