給定長度為 n（≤ 100）的整數序列 S，以及 m（≤ 100）條子序列和約束：
S[si] + … + S[si+ni] < ki 或 > ki。
判斷是否存在滿足所有約束的序列 S。
令前綴和 P[i] = S[1] + … + S[i]，P[0] = 0。
子序列和 = P[s+n] − P[s−1]。
lt（< k）→ P[s+n] − P[s−1] ≤ k−1 → 有向邊 (s−1) → (s+n) 權值 k−1。gt（> k）→ P[s+n] − P[s−1] ≥ k+1 → P[s−1] − P[s+n] ≤ −k−1 → 有向邊 (s+n) → (s−1) 權值 −k−1。共 n+1 個節點（0…n）。加入超級源點 n+1，向所有節點連邊權 0，確保圖連通。
若圖中存在負環，則差分約束系統無解，輸出 successful conspiracy；否則輸出 lamentable kingdom。
bool spfa() {
queue<int> q; vector<int> cnt(N+2, 0), inq(N+2, 0), dis(N+2, INF);
dis[super] = 0; q.push(super); inq[super] = 1; cnt[super] = 1;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u] = 0;
for (auto &e : G[u]) {
int v = e.to;
if (dis[v] > dis[u] + e.w) {
dis[v] = dis[u] + e.w;
if (!inq[v]) {
q.push(v); inq[v] = 1;
if (++cnt[v] > N+1) return false; // 負環
}
}
}
}
return true;
}
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge { int to, w; };
int main() {
int n, m;
while (scanf("%d", &n) && n) {
scanf("%d", &m);
vector<vector<Edge>> G(n + 2);
auto add = [&](int u, int v, int w) { G[u].push_back({v, w}); };
for (int i = 0; i < m; ++i) {
int s, ni, k; char op[3];
scanf("%d%d%s%d", &s, &ni, op, &k);
if (op[0] == 'g') // gt
add(s + ni, s - 1, -(k + 1));
else // lt
add(s - 1, s + ni, k - 1);
}
int super = n + 1;
for (int i = 0; i <= n; ++i) add(super, i, 0);
// SPFA
vector<int> dis(n + 2, INF), cnt(n + 2, 0), inq(n + 2, 0);
queue<int> q; dis[super] = 0; q.push(super); inq[super] = 1; cnt[super] = 1;
bool ok = true;
while (!q.empty() && ok) {
int u = q.front(); q.pop(); inq[u] = 0;
for (auto &e : G[u]) {
int v = e.to;
if (dis[v] > dis[u] + e.w) {
dis[v] = dis[u] + e.w;
if (!inq[v]) {
q.push(v); inq[v] = 1;
if (++cnt[v] > n + 1) { ok = false; break; }
}
}
}
}
puts(ok ? "lamentable kingdom" : "successful conspiracy");
}
return 0;
}
節點 ≤ 101，邊 ≤ 100 + 101，SPFA 極快。多測試案例總時間遠小於限制。
