TopCoder

Caido
Waimai

User's AC Ratio

100.0% (18/18)

Submission's AC Ratio

43.1% (31/72)

Tags

Description

國際刷牙奧林匹亞(International Olympiad in tooth brushIng,簡稱 IOI),是一年一度舉辦的國際競賽,目的是在考驗選手的刷牙能力,臺灣國際刷牙奧林匹亞(Taiwan Olympiad in tooth brushIng,簡稱 TOI),每年會選出一位刷牙很強的國手代表臺灣參賽。
這裡是 TOI,由於我們 IOI 2024 的刷牙選手 SJY 攜帶電動牙刷進入考場而被取消資格,已緊急從建中徵招職業刷牙選手 SJY (Shih GPow),沖擊 IOI 2025 滿分金。

IOI 2025 Day 1 Problem 1 如下:有 n 排牙齒,每排牙齒有 m 顆,第 i 排的第 j 顆牙齒有一個整數的爽度 ai,jai,j 可能有正有負,ai,j0 代表刷了牙齒變乾淨會很開心,ai,j<0 代表刷了會牙齒痛。

SJY 要在第 i 排的牙齒選一個區間 [li,ri]1lirim) 刷牙,他的爽適度 S 會是每排牙齒選的區間的爽度總和,也就是 S=i=1nj=liriai,j,並且 SJY 第 i1i<n) 排牙齒選的區間要滿足一個條件:[li,ri] 包含 [li+1,ri+1] 或是[li+1,ri+1] 包含 [li,ri](如果刷牙區間沒有包含關係會導致牙齦流血),也就是對於所有 1i<n,要滿足 1lili+1ri+1rim 或是 1li+1liriri+1m

題目要求 SJY 每排選的刷牙區間在滿足條件下,爽適度 S 最大,請你幫幫他!

Input Format

第一行有兩個正整數 n,m,代表有幾排牙齒和每排牙齒有幾顆。
接下來 n 行,第 i 行有 m 個整數 ai,1ai,m,代表第 i 排牙齒的爽度。

對於所有測試資料:

  • 1n,m500
  • 109ai,j109

Output Format

輸出一個整數 S,代表 SJY 每排選的刷牙區間在滿足條件下,爽適度的最大值。

Sample Input 1

1 5
-8 4 -1 2 -5

Sample Output 1

5

Sample Input 2

3 3
8 8 8
8 -141 8
8 8 8

Sample Output 2

56

Sample Input 3

6 8
476944489 774542013 452070325 861333371 -83858883 -512833211 681549195 693022218
-922334866 -532239730 927145932 -682553658 631797090 -747341551 -548567105 355222897
435055696 709399682 -684590943 -667612857 467023120 -892412460 -149231532 423472355
567036967 240648892 -906803104 -144866214 190666768 885683406 -608655819 -189225996
-528898393 -977898040 396168981 138998268 -825744423 479885502 384013409 -688712035
699272853 -807592000 -495299955 131616798 -983993952 257449280 -61141044 562361279

Sample Output 3

7001087192

Hints

在範例測資一中,第 1 排牙齒選的刷牙區間 [l1,r1]=[2,4] 可以得到最大的 S=4+(1)+2=5

在範例測資二中,3 排牙齒選的刷牙區間分別為 [1,3],[1,1],[1,3] 可以得到最大的 S=56

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0, 3~18 n=1 12
3 1, 5, 13~40 恰好存在一個 ai,j<0,其餘都 0 16
4 0~5, 41~50 n,m70 27
5 0~60 無其他限制 45

Testdata and Limits

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