41 . 8e7 與他的變數們

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

62.5% (5/8)

Submission's AC Ratio

15.7% (8/51)

Tags

ioicamp ioicamp-2024

Description

8e7 手上有 N 個變數，他可以任意的賦予這些變數介在 [0,105] 之間的整數值，但為此他可能得付出一些代價！

已知總共有 M 條規則控制著 8e7 得付出的代價，當第 i 條規則被滿足時，8e7 就會被迫花費 wi，而規則本身則可能會是以下三種形式之一：

  • 1 a p：代表該規則會被滿足當變數 a 的值 ≤p
  • 2 b q：代表該規則會被滿足當變數 b 的值 ≥q
  • 3 c r d s：代表該規則會被滿足當變數 c 的值 ≤r 且變數 d 的值 ≥s

你能告訴 8e7 在最佳的變數賦值情況下，他需要付出的最小代價總和嗎？當然，如果能告訴他一種賦值方式就更好了！

Input Format

輸入首行有兩個整數 N,M，代表變數的個數以及規則的個數。

接下來一行 M 個數字 w1,w2,…,wM，代表當第 i 條規則被滿足時，8e7 必須付出 wi 的代價。

緊接著 M 行，第 i 行代表第 i 條規則的滿足條件，其形式會如題敘內寫的呈現。

  • 1≤N,M≤500
  • 1≤wi≤106
  • 1≤a,b,c,d≤N
  • 0≤p,r<105
  • 0<q,s≤105

Output Format

首行輸出一行一個整數，代表 8e7 在最佳的變數賦值情況下，他需要付出的最小代價總和。

接下來一行 N 個整數 v1,v2,…,vN 以單一空格間隔隔開，代表你提供的一種最佳的變數賦值方法，滿足變數 i 的值為 vi。

在最小代價總和輸出正確後，你的答案會被視為正確若且唯若當你提供的變數賦值滿足：

  • 0≤vi≤105
  • 該變數賦值滿足的規則代價總和為最小代價總和

而若有多種賦值方法，輸出任何一種皆會視為正確。

  • 當你的最小代價總和輸出正確，但輸出的賦值方法不正確時，你依然可以獲得一半的分數。但請注意，你一定要輸出隨意一種賦值方法，也就是說，只輸出一行最小代價總和是不會獲得分數的，你必須至少例如直接在第二行輸出 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≤p,r<1,0<q,s≤1 40
3 19~33 N≤50,0≤p,r<10,0<q,s≤10 40
4 0~55 無額外限制 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 4
1 1000 262144 65536 1 4
2 1000 262144 65536 2 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 2 4
7 1000 262144 65536 2 4
8 1000 262144 65536 2 4
9 1000 262144 65536 2 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 2 4
14 1000 262144 65536 2 4
15 1000 262144 65536 2 4
16 1000 262144 65536 2 4
17 1000 262144 65536 2 4
18 1000 262144 65536 2 4
19 1000 262144 65536 3 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 3 4
29 1000 262144 65536 3 4
30 1000 262144 65536 3 4
31 1000 262144 65536 3 4
32 1000 262144 65536 3 4
33 1000 262144 65536 3 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
38 1000 262144 65536 4
39 1000 262144 65536 4
40 1000 262144 65536 4
41 1000 262144 65536 4
42 1000 262144 65536 4
43 1000 262144 65536 4
44 1000 262144 65536 4
45 1000 262144 65536 4
46 1000 262144 65536 4
47 1000 262144 65536 4
48 1000 262144 65536 4
49 1000 262144 65536 4
50 1000 262144 65536 4
51 1000 262144 65536 4
52 1000 262144 65536 4
53 1000 262144 65536 4
54 1000 262144 65536 4
55 1000 262144 65536 4
Submit
Back to Top