2383 . SJY 的國際刷牙奧林匹亞難題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (18/18)

Submission's AC Ratio

43.1% (31/72)

Tags

CKcon 2024-CKcon

Description

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

IOI 2025 Day 1 Problem 1 如下：有 $n$ 排牙齒，每排牙齒有 $m$ 顆，第 $i$ 排的第 $j$ 顆牙齒有一個整數的爽度 $a_{i,j}$，$a_{i,j}$ 可能有正有負，$a_{i,j}\ge 0$ 代表刷了牙齒變乾淨會很開心，$a_{i,j}<0$ 代表刷了會牙齒痛。

SJY 要在第 $i$ 排的牙齒選一個區間 $[l_i,r_i]$（$1\le l_i\le r_i\le m$） 刷牙，他的爽適度 $S$ 會是每排牙齒選的區間的爽度總和，也就是 $S=\sum\limits_{i=1}^ n\sum\limits_{j=l_i}^ {r_i}a_{i,j}$，並且 SJY 第 $i$（$1\le i<n$） 排牙齒選的區間要滿足一個條件：$[l_i,r_i]$ 包含 $[l_{i+1},r_{i+1}]$ 或是$[l_{i+1},r_{i+1}]$ 包含 $[l_i,r_i]$（如果刷牙區間沒有包含關係會導致牙齦流血），也就是對於所有 $1\le i<n$，要滿足 $1\le l_i\le l_{i+1}\le r_{i+1}\le r_i\le m$ 或是 $1\le l_{i+1}\le l_i\le r_i\le r_{i+1}\le m$。

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

Input Format

第一行有兩個正整數 $n,m$，代表有幾排牙齒和每排牙齒有幾顆。
接下來 $n$ 行，第 $i$ 行有 $m$ 個整數 $a_{i,1}\sim a_{i,m}$，代表第 $i$ 排牙齒的爽度。

對於所有測試資料：

  • $1\le n,m\le 500$
  • $-10^ 9\le a_{i,j}\le 10^ 9$

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$ 排牙齒選的刷牙區間 $[l_1,r_1]=[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 恰好存在一個 $a_{i,j}<0$，其餘都 $\ge 0$ 16
4 0~5, 41~50 $n,m\le 70$ 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
Submit
Back to Top