[COI 2021] Autobahn

Luogu

IDLGP8387

Time1000ms

Memory512MB

Difficulty—

2021COI（克罗地亚）

**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T1「[Autobahn](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」** 有 $N$ 个人在赛车场疾驰，第 $i$ 个人从第 $l_i$ 小时初疾驰到第 $r_i$ 小时末。鉴于赛车场要恰钱，每疾驰一小时交一块钱，然而这 $N$ 个人都只付了前 $t_i$ 个小时的钱。管理员十分仁慈，他们只会在有至少 $K$ 个人在赛车场上疾驰时来收额外的钱。赛车场搞活动，要求划分出一个长为 $X$ 小时的时间段，在这个时间段内如果有人需要被补交钱，则他不需要补交对应时间段欠的钱。赛车场希望活动使这 $N$ 个人不需要补交的钱最多，求出这个钱数。 ## Input 第一行三个整数 $N$，$K$，$X$。接下来 $N$ 行，一行三个整数 $l_i$，$t_i$，$r_i$。 ## Output 仅输出一行一个整数，表示您的答案。 [samples] ## Note 【样例解释】样例 #1 解释：所划分出的时间段为 $[4,7]$，这之中第一个人不需要交第 $4$ 小时的费用，而第二、三、四个人不需要交第 $6$，$7$ 个小时的费用。样例 #2 解释：所划分出的时间段为 $[12,33]$。【数据范围】对于 $100\%$ 的数据有 $1\le K\le N\le10^5$，$1\le X,l_i,t_i,r_i\le 10^9$，$l_i\le r_i$。 | Subtask | 限制 | 分数 | | :-----: | :-------------------------: | :--: | | $1$ | $N,K,X,l_i,t_i,r_i\le 100$ | $20$ | | $2$ | $N,K,X,l_i,t_i,r_i\le 10^3$ | $30$ | | $3$ | 无特殊限制 | $50$ |

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[COI 2021] Autobahn",
    "description": {
      "content": "**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T1「[Autobahn](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」** 有 $N$ 个人在赛车场疾驰，第 $i$ 个人从第 $l_i$ 小时初疾驰到第 $r_i$ 小时末。 鉴于赛车场要恰钱，每疾驰一小",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8387"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T1「[Autobahn](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」**\n\n有 $N$ 个人在赛车场疾驰，第 $i$ 个人从第 $l_i$ 小时初疾驰到第 $r_i$ 小时末。\n\n鉴于赛车场要恰钱，每疾驰一小...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments