TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

67.4% (29/43)

Submission's AC Ratio

40.5% (49/121)

Description

抓寶桌遊打算在市區開N 家連鎖店。可以開連鎖店的位置是M x M 的網格,每一家連鎖店必須開在不同的網格上,而且第二家連鎖店必須開在第一家的東北方,第三家連鎖店必須開在第二家的東北方,依此類推。東北方的定義爲X 座標和Y 座標都比較大。X 座標和Y 座標均介於0 到 M - 1。如果第 i 家 (i 介於0 到 N - 1)連鎖店開在 (x, y) 的位置則會有 ((ai + bx + cy) mod d) 的顧客。請寫一個程式決定N 家連鎖店的位置,使得所有連鎖店的顧客數總和為最大。

Input Format

輸入爲一行六個正整數:M N a b c d,1 ≤ a, b, c ≤ 2,000,1 ≤ d ≤ 1,200,000,兩整數間皆有一個空白。

Output Format

輸出爲一整數,代表所有連鎖店的顧客數總和的最大值。

Sample Input

4 2 1 2 3 17

Sample Output

26

Hints

本題共有兩個子題,每一子題可有多筆測試資料:
第一子題的測試資料 1 ≤ M ≤ 20,1 ≤ N ≤ 10 ,全部解出可獲37 分
第二子題的測試資料 1 ≤ M ≤ 200,1 ≤ N ≤ 100,全部解出可獲63 分

Problem Source

105學年度高級中學資訊學科能力競賽決賽 程式設計試題第一題

Subtasks

For Testdata: 0 ~ 9, Score: 37
For Testdata: 0 ~ 19, Score: 63
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 512
1 1000 524288 512
2 1000 524288 512
3 1000 524288 512
4 1000 524288 512
5 1000 524288 512
6 1000 524288 512
7 1000 524288 512
8 1000 524288 512
9 1000 524288 512
10 1000 524288 512
11 1000 524288 512
12 1000 524288 512
13 1000 524288 512
14 1000 524288 512
15 1000 524288 512
16 1000 524288 512
17 1000 524288 512
18 1000 524288 512
19 1000 524288 512