满分解法（100 分）

先看时间关系，而不是把所有重量相加

普通背包只关心被选物品的总重量。本题中，已经取出的物品不再占用承重，而且只有栈顶物品能取出，因此既要处理时间关系，又要处理堆叠关系。

将物品 $i$ 的存放过程记为时间区间 $[in_i,out_i)$。若两件被选物品满足

$$in_i<in_k<out_i<out_k,$$

那么 $k$ 放入时位于 $i$ 上面；到 $out_i$ 时，$k$ 尚未取出，导致 $i$ 无法从栈顶取出。因此这种严格交叉不能出现。

合法方案中的两个区间只能互不重叠，或一个包含另一个。端点相等不造成冲突：前一件可以先取出，后一件再放入；起点相等时先放入较晚取出的物品，终点相等时先取出较晚放入的物品。相同起止时刻的两件物品已经被题目排除。

用底部物品固定一整套方案

假设物品 $i$ 已经被选中。考虑它本身，以及在它存放期间曾经放在它上方的所有被选物品，称为一套以 $i$ 为底部的方案。

下层物品不需要知道这套方案内部的所有操作，只需要知道它的时间区间，以及任意时刻最多有多重。于是定义

$$f(i,c)=\text{必须选择物品 }i\text{，以它为底部，任意时刻总重量至多为 }c\text{ 的最大价值},$$

其中 $0\le c\le S$，价值包括 $v_i$。这里的 $c$ 是上界，不是要求峰值重量恰好等于 $c$。

当 $c<w_i$ 时，连物品 $i$ 自身都放不下，令 $f(i,c)=-\infty$。当 $c\ge w_i$ 时，物品 $i$ 上方的物品必须同时满足两项限制：不能超过它的承重 $s_i$，也不能连同它自身一起超过 $c$。所以上方可用的重量上界为

$$B=\min(s_i,c-w_i).$$

这说明为什么状态只需一个重量上界：来自背包和各层承重的限制，在进入下一层时都可以合并为这个最小值。

同一底部上的几套方案，要按时间拼接

在一套以 $i$ 为底部的方案中，将所有曾经直接压在 $i$ 上面的物品列出来。每个这样的物品 $k$，连同它上方的物品，又构成一套以 $k$ 为底部的方案。

这些直接上层物品的时间区间互不重叠。否则，在两个物品同时存在时，后放入的那个会压在先放入的那个上面，而不可能仍然直接压在 $i$ 上面。

因此，只需选出若干个互不重叠、且包含于 $i$ 区间内的物品区间。区间 $k$ 的收益取为 $f(k,B)$，再把这些收益相加。这里没有“将容量分给不同区间”的背包合并，因为它们不会同时存在，都能使用完整的上界 $B$。

例如，底部物品存放于 $[0,6)$，重量为 $1$，承重为 $2$，整套方案的重量上界为 $3$。上面可以先放一套区间为 $[1,3)$、峰值重量为 $2$、收益为 $7$ 的方案，再放一套区间为 $[3,5)$、峰值重量为 $2$、收益为 $9$ 的方案。在时刻 $3$ 先取出前一套，再放入后一套，上方峰值仍是 $2$，收益却可以累加为 $16$。把两套方案的重量相加成 $4$，反而会误判。

内层使用按结束时刻推进的动态规划

固定 $i,c$ 和相应的 $B$。定义

$$g_{i,c}(t)=\text{在物品 }i\text{ 上方，选取若干套不重叠且不晚于 }t\text{ 结束的方案的最大总价值}.$$

时间范围为 $in_i\le t\le out_i$。初始时尚未选择上层方案：

$$g_{i,c}(in_i)=0.$$

对于每个后续整数时刻 $t$，可以不在该时刻结束新的方案，也可以把一个结束于 $t$ 的方案 $k$ 接在先前方案之后：

$$g_{i,c}(t)=\max\left( g_{i,c}(t-1),\quad \max_{\substack{k\ne i,\ in_k\ge in_i,\ out_k=t\le out_i\\ w_k\le B}} \bigl(g_{i,c}(in_k)+f(k,B)\bigr) \right).$$

内层候选必须是包含于 $i$ 的真子区间；没有候选时只保留第一项。$g_{i,c}(in_k)$ 允许前面的方案恰好在 $in_k$ 时刻结束，因为可以先取出，再放入 $k$。

于是

$$f(i,c)=v_i+g_{i,c}(out_i)\qquad(c\ge w_i).$$

不放任何上层物品时，所有 $g$ 都可以为 $0$，对应仅选择 $i$。代码中的 dp[i][c] 对应 $f(i,c)$，dp_time[t] 对应当前固定 $i,c$ 的 $g_{i,c}(t)$。

这一转移既没有遗漏也不会引入非法方案。任意合法堆叠都能按直接上层物品拆成上述不重叠的几套方案；反过来，每套方案内部合法，彼此在时间上不重叠，且峰值都不超过 $B$，拼接后就同时满足物品 $i$ 的承重和整套方案的重量上限。因此对子问题按依赖顺序求最优，得到的也是当前状态的最优值。

先计算被包含的区间

将所有物品按照 $out_i$ 递增排序，$out_i$ 相同时按照 $in_i$ 递减排序。

如果 $k$ 的区间被 $i$ 真包含，那么或者 $out_k<out_i$，或者 $out_k=out_i$ 且 $in_k>in_i$。两种情况下，$k$ 都排在 $i$ 前面，所以计算 $f(i,c)$ 时，需要的 $f(k,B)$ 已经求出。

实现中，对于当前物品 $i$，按排序顺序扫描它之前的物品 $k$，只保留 $in_k\ge in_i$ 的候选。排序已经保证 $out_k\le out_i$，不需要再枚举全部时间区间。

使用指针从 $in_i$ 向后推进：到下一个候选的结束时刻之前，每一步先继承前一时刻的最优值；到结束时刻后，再执行相应的拼接转移。同一结束时刻的多个候选取最大值。由于 $in_k<out_k$，读取的 $g_{i,c}(in_k)$ 已经定稿，不会重复使用当前物品。

当前 $i,c$ 计算完成后，内层时间表可以供下一次独立计算复用；所有外层状态 $f(i,c)$ 都保留。若最后一个候选结束后还剩一段空时间，最优值不再变化，无需继续逐时刻推进。

用一个虚拟底部得到总答案

增加一件只用于算法的虚拟物品 $r$：

$$in_r=0,\quad out_r=2n+1,\quad w_r=0,\quad s_r=S,\quad v_r=0.$$

它包含所有真实物品的区间，且最后被计算。所有原题方案都可以看成放在它上面的若干套方案，它自身不增加重量或价值，因此答案为

$$\boxed{f(r,S)}.$$

虚拟物品只是统一状态的边界处理，不是额外的输入物品，也不改变原题的时间范围。允许所有真实物品都不选，答案此时为 $0$。

复杂度

时间复杂度为 $O(n^2(S+1)+n\log n)$。共有 $O(n(S+1))$ 个外层状态，每个状态扫描至多 $n$ 个候选，时间指针总共前进至多 $2n+1$ 次；并不是每遇到一个候选都重新扫描整段时间。

空间复杂度为 $O(n(S+1)+n)$，用于保留全部外层状态、当前内层时间表和物品信息。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct item {
  int in, out, w, s, v;
};

void solve() {
  int n, cap;
  cin >> n >> cap;
  vector<item> a(n + 1);
  for (int i = 0; i < n; i++) {
    cin >> a[i].in >> a[i].out >> a[i].w >> a[i].s >> a[i].v;
  }
  a[n] = {0, 2 * n + 1, 0, cap, 0};
  sort(a.begin(), a.end(), [](item x, item y) {
    if (x.out != y.out) return x.out < y.out;
    return x.in > y.in;
  });

  constexpr int neg = INT_MIN / 2;
  vector<vector<int>> dp(n + 1, vector<int>(cap + 1, neg));
  vector<int> dp_time(2 * n + 2);
  for (int i = 0; i <= n; i++) {
    for (int j = a[i].w; j <= cap; j++) {
      int limit = min(a[i].s, j - a[i].w);
      int p = a[i].in;
      dp_time[p] = 0;
      for (int k = 0; k < i; k++) {
        if (a[k].in < a[i].in) continue;
        while (p < a[k].out) {
          dp_time[p + 1] = dp_time[p];
          p++;
        }
        if (a[k].w > limit) continue;
        dp_time[p] = max(dp_time[p], dp_time[a[k].in] + dp[k][limit]);
      }
      dp[i][j] = a[i].v + dp_time[p];
    }
  }
  cout << dp[n][cap] << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

同时放入时的承重背包（通过子任务 2，共 20 分）

相同放入时刻决定堆叠次序

本方法覆盖子任务 $2$：所有物品的 $in_i$ 相同。

由于任意两件物品不会同时具有相同的放入和取出时刻，这个子任务中所有 $out_i$ 互不相同。选择若干物品后，它们会同时留在背包中；较早取出的必须位于较上方。因此按 $out_i$ 递增排列，就是从顶部向底部建立堆叠的顺序。

最重的时刻是全部放入完成之后。以后的操作只有取出，只会减轻背包和各层物品的负担。因此无需记录时间，只要构造一个初始合法堆叠即可。

按总重量做0/1背包

将物品按 $out_i$ 递增排序。定义

$$h(i,j)=\text{从排序后的前 }i\text{ 件物品中选择，总重量恰为 }j\text{ 的合法堆叠的最大价值}.$$

初始条件为 $h(0,0)=0$，$h(0,j)=-\infty$（$j>0$）。

对于第 $i$ 件物品，可以不选择：

$$h(i,j)\gets h(i-1,j).$$

也可以把它加在已有堆叠的底部。若原堆叠总重量为 $j$，那么恰好就是新物品需要承受的重量，故需要 $j\le s_i$；连同它自身后的总重量还需满足 $j+w_i\le S$。满足条件且原状态可达时，有

$$h(i,j+w_i)\gets\max\bigl(h(i,j+w_i),h(i-1,j)+v_i\bigr).$$

已有物品上方的重量没有增加，所以它们原来的承重条件仍然成立；新底部比它们都晚取出，不会挡住它们。反过来，任意合法选择按取出时刻从早到晚依次加到底部，都能由这些转移构造。因此递推恰好覆盖全部合法方案。

答案为

$$\max_{0\le j\le S}h(n,j).$$

原地更新与边界

这是按物品进行的0/1背包，可以省去物品层，只保留按重量索引的状态。对于每件物品，从 $\min(s_i,S-w_i)$ 开始向下枚举旧重量 $j$，将旧状态更新到 $j+w_i$。

当 $w_i>0$ 时，倒序保证来源尚未被当前物品更新，避免一件物品被重复选择。当 $w_i=0$ 时，来源和目标相同，但每个重量状态只执行一次该物品的更新，因此仍只加入一次价值。不可达状态不能参加转移；重量超过 $S$ 的物品没有合法转移。

这个方法的关键前提是所有放入时刻相同。一般情况下，不同时段的物品可以复用背包容量，也可能因区间交叉而不能同时选择，因此不能直接忽略放入时刻。

复杂度

时间复杂度为 $O(n(S+1)+n\log n)$，空间复杂度为 $O(S+n)$，包括背包状态和排序所用的物品数组。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct item {
  int in, out, w, s, v;
};

void solve() {
  int n, cap;
  cin >> n >> cap;
  vector<item> a(n);
  for (auto& x : a) cin >> x.in >> x.out >> x.w >> x.s >> x.v;
  sort(a.begin(), a.end(), [](item x, item y) {
    return x.out < y.out;
  });

  constexpr int neg = INT_MIN / 2;
  vector<int> dp(cap + 1, neg);
  dp[0] = 0;
  for (auto& x : a) {
    for (int j = min(x.s, cap - x.w); j >= 0; j--) {
      if (dp[j] == neg) continue;
      dp[j + x.w] = max(dp[j + x.w], dp[j] + x.v);
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

维护堆叠的选取回溯（通过子任务 1，共 20 分）

适用范围

本方法覆盖子任务 $1$，即 $n\le 10$。直接对每件物品决定选或不选，并维护当前真实堆叠，可以枚举全部合法方案。

固定同一时刻的放入顺序

先按 $in_i$ 递增排序，放入时刻相同时按 $out_i$ 递减排序。两件物品同时放入时，较晚取出的必须在下面，否则它会挡住较早需要取出的物品。因此对任何被选子集，这种顺序都不损失合法方案。

维护一个从底部到顶部的栈。准备处理当前物品时，先弹出栈顶所有满足 $out_k\le in_i$ 的物品。相等时先取出再放入，符合题意。已有栈始终合法，所以到期物品上面的物品也都已到期，不会出现到期物品被未到期物品挡住的情况。

枚举选取，并检查全部下层承重

对于当前物品 $i$，始终可以选择跳过。选择放入时，需要检查以下条件。

若栈非空，当前栈顶的取出时刻必须不早于 $out_i$；否则新物品会在原栈顶应当取出时挡住它。

此外，从新物品的重量 $w_i$ 开始，沿栈从上往下累计重量。访问原物品 $k$ 时，当前累计量就是放入新物品后压在 $k$ 上方的总重量，必须不超过 $s_k$；检查后再加上 $w_k$，继续向下一层检查。最终累计量还必须不超过背包承重 $S$。

原有堆叠已经合法，取出物品只会减轻负担。因此只要每次放入都这样检查，所有时刻的承重就都合法。当前物品自身上方暂时为空；以后继续放入时，它的承重也会被逐层检查。

将合法的新物品压栈，递归处理后续物品，返回时恢复栈。处理所有物品后，以已选物品的价值之和更新答案。虽然代码在选择时累加价值，但取出次序已由上述检查保证合法，每件选中物品最终都能如期取出，因此等价于取出时计费。

跳过和放入两种分支覆盖所有子集，检查又准确排除了非法扩展，所以最终取到最大合法价值。空子集始终合法，初始答案为 $0$。程序没有针对大输入的截断；范围变大后可能因枚举数量过多而超时。

复杂度

时间复杂度为 $O(n2^n+n\log n)$，每次放入的合法性检查最多扫描 $n$ 个栈元素。

空间复杂度为 $O(n)$。递归深度至多 $n$；当前栈和各层暂存的已到期物品互不重复，每件物品在一条递归路径上至多属于其中一处，回溯时按相反顺序恢复。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct item {
  int in, out, w, s, v;
};

void solve() {
  int n, cap;
  cin >> n >> cap;
  vector<item> a(n);
  for (auto& x : a) cin >> x.in >> x.out >> x.w >> x.s >> x.v;
  sort(a.begin(), a.end(), [](item x, item y) {
    if (x.in != y.in) return x.in < y.in;
    return x.out > y.out;
  });

  vector<int> stk;
  int ans = 0;
  auto dfs = [&](auto&& self, int pos, int sum) -> void {
    if (pos == n) {
      ans = max(ans, sum);
      return;
    }
    vector<int> old;
    while (!stk.empty() && a[stk.back()].out <= a[pos].in) {
      old.push_back(stk.back());
      stk.pop_back();
    }
    self(self, pos + 1, sum);

    bool ok = stk.empty() || a[pos].out <= a[stk.back()].out;
    int load = a[pos].w;
    for (int i = (int)stk.size() - 1; i >= 0; i--) {
      int k = stk[i];
      if (load > a[k].s) ok = false;
      load += a[k].w;
    }
    if (load > cap) ok = false;
    if (ok) {
      stk.push_back(pos);
      self(self, pos + 1, sum + a[pos].v);
      stk.pop_back();
    }
    for (auto it = old.rbegin(); it != old.rend(); it++) stk.push_back(*it);
  };
  dfs(dfs, 0, 0);
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}