[AdditionalFile2688.zip](file://AdditionalFile2688.zip?type=additional_file)

P3592 [POI 2015 R3] 洗车 Car washes

题目描述

有 $n$ 家洗车店从左往右排成一排，每家店都有一个正整数价格 $p_i$。有 $m$ 个人要来消费，第 $i$ 个人会驶过第 $a_i$ 个开始一直到第 $b_i$ 个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 $c_i$，那么这个人就不洗车了。请给每家店指定一个价格，使得所有人花的钱的总和最大。

输入格式

第一行包含两个正整数 $n,m$（$1 \le n \le 50$，$1 \le m \le 4000$）。接下来 $m$ 行，每行包含三个正整数 $a_i,b_i,c_i$（$1 \le a_i \le b_i \le n$，$1 \le c_i \le 5\times 10^5$）。

输出格式

第一行输出一个正整数，即消费总额的最大值。第二行输出 $n$ 个正整数，依次表示每家洗车店的价格 $p_i$，要求 $1 \le p_i \le 5\times 10^5$。若有多组最优解，输出任意一组。

输入输出样例 #1

输入 #1

7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5

输出 #1

43
5 5 13 13 20 20 13

说明/提示

原题名称：Myjnie。

#2688. 「POI2015 R3」洗车 Car washes

标签: 传统 | 时间限制: 26000 ms | 内存限制: 256 MiB |

题目描述

译自 POI 2015 Stage 3. Day 1「Car washes」

有 $n$ 家洗车店从左往右排成一排，编号为 $1\sim n$，每家店都有一个正整数价格 $p_i$。

有 $m$ 个人要来消费，第 $i$ 个人会驶过从第 $a_i$ 个开始一直到第 $b_i$ 个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 $c_i$，那么这个人就不洗车了。

请给每家店指定一个价格，使得所有人花的钱的总和最大。

输入格式

第一行包含两个正整数 $n,m$。
接下来 $m$ 行，每行包含三个正整数 $a_i,b_i,c_i$。

输出格式

第一行输出一个正整数，即消费总额的最大值。
第二行输出 $n$ 个正整数，依次表示每家洗车店的价格 $p_i$。
若有多组最优解，输出任意一组。

样例

输入

7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5

输出

43
5 5 13 13 20 20 13

数据范围与提示

对于全部数据，$1\le n\le 50,1\le m\le 4000,1\le a_i\le b_i\le n,1\le c_i,p_i\le 5\times 10^5$。