TopCoder

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

User's AC Ratio

87.9% (87/99)

Submission's AC Ratio

33.4% (131/392)

Tags

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 512 1 2
1 1000 524288 512 1 2
2 1000 524288 512 1 2
3 1000 524288 512 1 2
4 1000 524288 512 1 2
5 1000 524288 512 1 2
6 1000 524288 512 1 2
7 1000 524288 512 1 2
8 1000 524288 512 1 2
9 1000 524288 512 1 2
10 1000 524288 512 2
11 1000 524288 512 2
12 1000 524288 512 2
13 1000 524288 512 2
14 1000 524288 512 2
15 1000 524288 512 2
16 1000 524288 512 2
17 1000 524288 512 2
18 1000 524288 512 2
19 1000 524288 512 2