1938 . 連鎖店 (Chains)
TopCoder
Description
抓寶桌遊打算在市區開 $N$ 家連鎖店。可以開連鎖店的位置是 $M\times M$ 的網格，每一家連鎖店必須開在不同的網格上，而且第二家連鎖店必須開在第一家的東北方，第三家連鎖店必須開在第二家的東北方，依此類推。東北方的定義爲 $X$ 座標和 $Y$ 座標都比較大。$X$ 座標和 $Y$ 座標均介於 $0$ 到 $M - 1$。如果第 $i$ 家 （$i$ 介於 $0$ 到 $N - 1$）連鎖店開在 $(x, y)$ 的位置則會有 $((ai + bx + cy)\text{ mod }d)$ 的顧客。請寫一個程式決定 $N$ 家連鎖店的位置，使得所有連鎖店的顧客數總和為最大。
Input Format
輸入爲一行六個正整數：$M\ N\ a\ b\ c\ d$，$1 ≤ a, b, c ≤ 2\times 10^ 3$，$1 ≤ d ≤ 1.2\times 10^ 6$，兩整數間皆有一個空白。
Output Format
輸出爲一整數，代表所有連鎖店的顧客數總和的最大值。
Sample Input 1
4 2 1 2 3 17
Sample Output 1
26
Hints
本題共有兩個子題，每一子題可有多筆測試資料：
第一子題的測試資料 $1 ≤ M ≤ 20$，$1 ≤ N ≤ 10$，全部解出可獲 $37$ 分
第二子題的測試資料 $1 ≤ M ≤ 200$，$1 ≤ N ≤ 100$，全部解出可獲 $63$ 分
Problem Source
105學年度高級中學資訊學科能力競賽決賽 程式設計試題第一題
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~9 | 37 |
| 2 | 0~19 | 63 |