副社長的休息時間

發布時間: Jan. 4, 2023, 5:49 p.m.   最後更新時間: Jan. 12, 2023, 10:33 p.m.   時間限制: 1000ms   記憶體限制: 128M

在忙碌的學校生活中,最讓副社長期待的莫過於放學了

由於他幾乎沒有補習,所以放學後只要回到家就都是他的休息時間

而他的休閒活動只有兩種,打code和打電動(特別是音遊)

如果你有像某教學李X霆一樣偷看過副社長的手機就會知道

在他手機內可是有千千百百種不同的音遊

雖然有很多不同的遊戲玩是件好事,可是休息時間有限,他一次也只能玩一種,沒有辦法全部都玩過一次,所以他希望知道玩音遊可以得到多高的滿足感以決定這次休息要打code還是打音遊

而在考社內賽的你成為了他的工具人,你需要寫出一份code幫他計算玩音遊最多可以得到的滿足感

計算方式如下

會先告訴你休息時間有多長和副社長有幾種音遊可以玩

接著會告訴你每種音遊的開始時間和結束時間還有可帶來的滿足感(對!副社長有自我規範,要玩就必須玩完!)

這樣聽起來不難吧,可是副社長覺得浪費休息時間太可惜了,所以他決定增加一條計算規則

有多長的時間沒在打音遊滿足度就要扣多少

如果不懂就看範例測資吧

第一行給兩的整數$t, n, t \leq 10^{18}, n \leq 10^3$代表休息時間有$t$且音遊有$n$種
接著會有$n$行輸入,每行會有三個整數$s_i, e_i, v_i, 0 \le s_i \le e_i \le n, v_i \leq 10^5$分別代表地$i$種音遊的開始時間、結束時間和帶來的滿足感
題目保證所有$s_i, e_i$都不同,也就是說不會有兩個音遊同時開始、同時結束或完美銜接

輸出一整數為副社長在休息時間結束時最多可有多少滿足感

複製範例
10 3
1 6 2
2 3 3
4 7 5
2

範例測資中最佳解為遊玩第二和第三種音遊

共可獲得$8$的滿足感,並有$0$到$2$, $3$到$4$, $7$到$10$三段時間沒有在玩遊戲,所以扣掉$2+1+3 = 6$,故答案為$2$

以下是你可能會用到到沒教過的東西

1.struct 語法如下

struct name{

type value;

type value;

......

};

簡單來說他可以把很多資料打包在一起變成新的資料型態,須寫在使用前(和函式的宣告一樣),注意最後的分號

取值:

假如有一struct如下

struct line{

int M;

int B;

};

我們有

line a;

則你可以改變a的M和B,方法如下

a.M = 2;(把a的M變成2)

取值則是

cout << a.M(輸出a的M是多少)


2.sort函式 語法如下

排序n格的陣列:sort(arr, arr+n)

預設由小排到大 ,可自定義排序的方法,需先寫一bool函式並列在最後面

如sort(arr, arr+n, comp),其中comp為bool函式的名稱

例如:

bool comp(int a, int b){

return a > b;

}

sort(arr, arr+n, comp)

則arr會被由大排到小


請注意範圍喔

dp

竹中軟研38th第二次競賽(社內暨日麻成就賽)