比赛 2026.1.8 评测结果 WWTTTTTTTTTTTTTTTTTT
题目名称 区间价值 最终得分 0
用户昵称 LikableP 运行时间 19.811 s
代码语言 C++ 内存使用 2.14 MiB
提交时间 2026-01-08 20:48:37
显示代码纯文本
#include <cstdio>
#include <algorithm>

const int MAXN = 1e5 + 10;

int n;
struct Seq { int l, r, w; } a[MAXN];
int choose[MAXN], ccnt;
int ans;

bool Touch(Seq a, Seq b) {
  if (b.l <= a.l && a.l <= b.r) return true;
  if (b.l <= a.r && a.r <= b.r) return true;
  return false;
}

bool canPlace(Seq x) {
  for (int i = 1; i <= ccnt; ++i) {
    if (Touch(x, a[i])) return false;
  }
  return true;
}

void dfs(int step, int now) {
  ans = std::max(ans, now);
  if (step > n) return ;
  if (canPlace(a[step])) {
    choose[++ccnt] = step;
    dfs(step + 1, now + a[step].w);
    --ccnt;
  } 

  dfs(step + 1, now);
}

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("sum.in", "r", stdin);
    freopen("sum.out", "w", stdout);
  #endif

  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d %d", &a[i].l, &a[i].r, &a[i].w);
  }

  std::sort(a + 1, a + n + 1, [](Seq x, Seq y) {
    if (x.l != y.l) return x.l < y.l;
    return x.r < y.r;
  });

  dfs(1, 0);

  printf("%d\n", ans);
  return 0;
}