以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Treatment Project
治療計画(Treatment Project)
JOI 国にはN 軒の家があり,1 からN までの番号が付けられている.これらの家は番号順に一列に並ん
でおり,各家には1 人の国民が住んでいる.家x に住んでいる国民を国民x と表す(1 ≦x ≦N).
今,新型のウイルスが発生してすべての国民がウイルスに感染してしまった.この事態に対しM 個の治
療計画が提案された.計画i (1 ≦i ≦M) の実施にはコストがCi だけかかる. 計画i を実施すると次のこと
が起こる.
今からTi 日後の夕方にLi ≦x ≦Ri を満たす国民x がもしウイルスに感染していれば治療される.
また,ウイルスは隣り合う国民の間で次のように伝染する.
ある日の朝に国民x (1 ≦x ≦N) がウイルスに感染しているなら,その日の昼に国民x −1 (x ≧2 の
場合) と国民x + 1 (x ≦N −1 の場合) もウイルスに感染する.
一度治療された国民も再度感染する可能性がある.
JOI 国の大臣であるあなたは,いくつかの計画を実施して次の条件を満たすようにしたい.
条件 計画がすべて実施された後,どの国民もウイルスに感染していない.
ただし,同じ日に2 つ以上の計画を実施することもできる.
家の軒数と治療計画の情報が与えられたとき,上の条件を満たすことができるかを判定し,もし満たすこ
とができる場合は必要なコストの合計の最小値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M
T1 L1 R1 C1
...
TM LM RM CM
出力
標準出力に1 行で出力せよ.条件を満たすことができないなら−1 を出力せよ.条件を満たすことができ
る場合は,必要なコストの合計の最小値を出力せよ.
治療計画– 1 / 3
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Treatment Project
制約
• 1 ≦N ≦1 000 000 000.
• 1 ≦M ≦100 000.
• 1 ≦Ti ≦1 000 000 000 (1 ≦i ≦M).
• 1 ≦Li ≦Ri ≦N (1 ≦i ≦M).
• 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦M).
小課題
1. (4 点) Ti = 1 (1 ≦i ≦M).
2. (5 点) M ≦16.
3. (30 点) M ≦5 000.
4. (61 点) 追加の制約はない.
入出力例
入力例1 出力例1
10 5 7
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
入力例1 では次のように計画を実施すればよい.
• 2 日後の夕方に計画1 を実施して国民5, 6, 7, 8, 9, 10 を治療する. 感染した国民は1, 2, 3, 4 となる.
• 3 日後の昼に国民5 が感染する. 感染した国民は1, 2, 3, 4, 5 となる.
• 4 日後の昼に国民6 が感染する. 感染した国民は1, 2, 3, 4, 5, 6 となる.
• 4 日後の夕方に計画5 を実施して国民1, 2, 3 を治療する. 感染した国民は4, 5, 6 となる.
• 5 日後の昼に国民3, 7 が感染する. 感染した国民は3, 4, 5, 6, 7 となる.
• 5 日後の夕方に計画3 を実施して国民3, 4, 5, 6, 7 を治療する. これによりすべての国民がウイルスに
感染していない状態になる.
治療計画– 2 / 3
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Treatment Project
計画1, 3, 5 を実施するのに必要なコストの合計は7 である. 条件を満たすように, どのように計画を実施
してもコストの合計を7 より小さくすることはできないので7 を出力する.
入力例2 出力例2
10 5 -1
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1
入力例2 ではどのように計画を実施しても条件を満たすことができないので−1 を出力する.
入力例3 出力例3
10 5 7
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1
この入力例は小課題1 の制約を満たす.
治療計画– 3 / 3