package main import . "fmt" import . "os" import bf "bufio" // まさかIOでTLE...ですか!? func main() { rd:=bf.NewReader(Stdin) var n,m int Fscan(rd,&n,&m) dp := make([]int, 2) for i := 0; i < n; i++ { sum := 0 for k := 0; k < m; k++ { var a int Fscan(rd,&a) sum += a } dp[0],dp[1] = max(dp[0],dp[1]+sum,sum),max(dp[1],dp[0]-sum) } Println(max(dp[0],dp[1])) } /* 考察 これ子供の区別は必要か?と思ったら どうもコンテスト時は同じ問題タイトルで難易度の違う問題が出ていたようで フォーマットの統一感を出すためなのかもしれない 他の難易度の問題では区別して計算する必要があるのだと思う(他の問題はまだ見てないけど) i番目を取る取らないのシンプルなDP問題ぽい DP[i番目][i番目時点での幸せ度最大の食べた回数の偶奇] = 最大の幸せ度 で DP[i][奇数] = max(DP[i-1][奇数], DP[i-1][偶数] + sum(Ai1..AiM), sum(Ai1..AiM)) DP[i][偶数] = max(DP[i-1][偶数], DP[i-1][奇数] - sum(Ai1..AiM)) で更新かな もうすこし強いサンプルが欲しかったかも */