41 . 8e7 與他的變數們
TopCoder
.jpg)
Tags
Description
8e7 手上有 $N$ 個變數，他可以任意的賦予這些變數介在 $[0, 10^ 5]$ 之間的整數值，但為此他可能得付出一些代價！
已知總共有 $M$ 條規則控制著 8e7 得付出的代價，當第 $i$ 條規則被滿足時，8e7 就會被迫花費 $w_i$，而規則本身則可能會是以下三種形式之一：
- $1\ a\ p$：代表該規則會被滿足當變數 $a$ 的值 $\leq p$
- $2\ b\ q$：代表該規則會被滿足當變數 $b$ 的值 $\geq q$
- $3\ c\ r\ d\ s$：代表該規則會被滿足當變數 $c$ 的值 $\leq r$ 且變數 $d$ 的值 $\geq s$
你能告訴 8e7 在最佳的變數賦值情況下，他需要付出的最小代價總和嗎？當然，如果能告訴他一種賦值方式就更好了！
Input Format
輸入首行有兩個整數 $N, M$，代表變數的個數以及規則的個數。
接下來一行 $M$ 個數字 $w_1, w_2, \ldots, w_M$，代表當第 $i$ 條規則被滿足時，8e7 必須付出 $w_i$ 的代價。
緊接著 $M$ 行，第 $i$ 行代表第 $i$ 條規則的滿足條件，其形式會如題敘內寫的呈現。
- $1 \leq N, M \leq 500$
- $1 \leq w_i \leq 10^ 6$
- $1 \leq a, b, c, d \leq N$
- $0 \leq p, r < 10^ 5$
- $0 < q, s \leq 10^ 5$
Output Format
首行輸出一行一個整數，代表 8e7 在最佳的變數賦值情況下，他需要付出的最小代價總和。
接下來一行 $N$ 個整數 $v_1, v_2, \ldots, v_N$ 以單一空格間隔隔開，代表你提供的一種最佳的變數賦值方法，滿足變數 $i$ 的值為 $v_i$。
在最小代價總和輸出正確後，你的答案會被視為正確若且唯若當你提供的變數賦值滿足：
- $0 \leq v_i \leq 10^ 5$
- 該變數賦值滿足的規則代價總和為最小代價總和
而若有多種賦值方法，輸出任何一種皆會視為正確。
- 當你的最小代價總和輸出正確，但輸出的賦值方法不正確時，你依然可以獲得一半的分數。但請注意，你一定要輸出隨意一種賦值方法，也就是說，只輸出一行最小代價總和是不會獲得分數的，你必須至少例如直接在第二行輸出 $N$ 個 $0$ 才可以通過 checker 的檢查。
Sample Input 1
3 6 2 3 3 8 1 4 1 2 0 1 3 0 2 1 1 2 3 1 3 3 0 2 1 3 3 0 1 1
Sample Output 1
4 0 1 0
Sample Input 2
3 7 10 5 2 2 3 1 9 1 3 3 3 2 9 3 10 2 3 1 1 1 0 2 2 9 3 1 1 2 10 2 1 2
Sample Output 2
2 1 8 4
Hints
Problem Source
IOICamp 2024 Day4 pH
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~18 | $0 \leq p, r < 1, 0 < q, s \leq 1$ | 40 |
| 3 | 19~33 | $N \leq 50, 0 \leq p, r < 10, 0 < q, s \leq 10$ | 40 |
| 4 | 0~55 | 無額外限制 | 20 |