import times, strutils, sequtils, math, algorithm, tables, sets, lists, intsets import critbits, future, strformat, deques template `max=`(x,y) = x = max(x,y) template `min=`(x,y) = x = min(x,y) template `mod=`(x,y) = x = x mod y template scan2 = (scan(), scan()) template scan3 = (scan(), scan()) let read* = iterator: string {.closure.} = while true: (for s in stdin.readLine.split: yield s) proc scan(): int = read().parseInt proc scanf(): float = read().parseFloat proc toInt(c:char): int = return int(c) - int('0') proc solveDP():int= var (n,m,a)=(scan(),scan(),scan()) lrp = newseqwith(m,(scan(),scan(),scan())) le = newseqwith(n+2,newseq[int]()) re = newseqwith(n+2,newseq[int]()) dp = newseqwith(n+2,newseqwith(2,-int.high.div(4))) lrp = lrp.sorted() dp[1][1]=0 for idx,(l,r,p) in lrp: le[l].add(idx) re[r].add(idx) for i in 1..n+1: #echo "i:", i if i>1: dp[i][0].max=max(dp[i-1][0],dp[i-1][1]) dp[i][1].max=max(dp[i-1][0],dp[i-1][1])-a for idx in le[i]: #echo lrp[idx] if lrp[idx][1]==n: dp[lrp[idx][1]+1][1].max=max(lrp[idx][2]+dp[i][1],lrp[idx][2]+dp[i][0]-a) else: dp[lrp[idx][1]+1][1].max=max(lrp[idx][2]+dp[i][1],lrp[idx][2]+dp[i][0]-a)-a #echo dp.join("\n") #echo "###" return dp[n+1].max() proc solve():int= var (n,m,a)=(scan(),scan(),scan()) lrp = newseqwith(m,(scan()-1,scan()-1,scan())) le = newseqwith(n+1,newseq[int]()) re = newseqwith(n+1,newseq[int]()) memo = initTable[(int,int,),int]() lrp = lrp.sorted() for idx,(l,r,p) in lrp: le[l].add(idx) re[r].add(idx) # l-1とlのあいだ、rとr+1の間に黒線が存在するケース proc recSolve(l,r:int):int= echo l,", ", r if memo.hasKey((l,r)): return memo[(l,r)] for idx in le[l]: if lrp[idx][1]==r: result.max=lrp[idx][2] # for m in l..