[COCI 2022/2023 #1] Neboderi

Luogu

IDLGP9032

Time2500ms

Memory512MB

DifficultyP5

动态规划 DP2022数论ST 表COCI（克罗地亚）

这排摩天大楼共有 $n$ 座，它们可以被视作序列 $h_1,h_2,...h_n$，其中 $h_i$ 为第 $i$ 栋楼的高度。Domagoj 将会拍下这排大楼的一个子区间。为了更好地捕捉城市之美，他想拍摄至少 $k$ 座摩天大楼。 Domagoj 有着奇怪的审美：他认为照片中有高大的摩天大楼是美的；但如果照片中所有的摩天大楼的高度有着很大的公因数，他会认为更美。如果一张照片拍下的大楼区间为 $[l,r]$，且这段区间内所有大楼高度的 $\gcd$ 为 $g$，则 Domagoj 定义这张照片的“美丽度”为 $g \times \sum_{i=l}^r h_i$。帮助 Domagoj 算出他能拍到的最美照片的美丽度吧！ ## Input 第一行包含两个整数 $n,k$，分别表示大楼总数和 Domagoj 至少拍到的大楼数。第二行包含 $n$ 个整数 $h_i$，依次表示每座大楼的高度。 ## Output 一行一个整数，即最大美丽值。 [samples] ## Background Domagoj 来到了伦敦这个大城市！现在有一排高摩天大楼在他面前，他想拍张照片来纪念这一时刻。 ## Note | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $11$ | $n,k \leq 100$ | | $2$ | $22$ | $n,k \leq 5000$ | | $3$ | $27$ | $k \leq 100$ | | $4$ | $18$ | $n,k \leq 5\times 10^4$ | | $5$ | $32$ | 无特殊性质 | 对于 $100\%$ 的数据，满足 $1\leq k \leq n \leq 10^6,1\leq h_i \leq 10^6$。本题满分 $110$ 分。

Samples

Input #1

6 2
2 1 4 4 4 2

Output #1

Input #2

4 1
7 3 9 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #1] Neboderi",
    "description": {
      "content": "这排摩天大楼共有 $n$ 座，它们可以被视作序列 $h_1,h_2,...h_n$，其中 $h_i$ 为第 $i$ 栋楼的高度。Domagoj 将会拍下这排大楼的一个子区间。为了更好地捕捉城市之美，他想拍摄至少 $k$ 座摩天大楼。 Domagoj 有着奇怪的审美：他认为照片中有高大的摩天大楼是美的；但如果照片中所有的摩天大楼的高度有着很大的公因数，他会认为更美。 如果一张照片拍下的大楼区间为",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9032"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "这排摩天大楼共有 $n$ 座，它们可以被视作序列 $h_1,h_2,...h_n$，其中 $h_i$ 为第 $i$ 栋楼的高度。Domagoj 将会拍下这排大楼的一个子区间。为了更好地捕捉城市之美，他想拍摄至少 $k$ 座摩天大楼。\n\nDomagoj 有着奇怪的审美：他认为照片中有高大的摩天大楼是美的；但如果照片中所有的摩天大楼的高度有着很大的公因数，他会认为更美。\n\n如果一张照片拍下的大楼区间为...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments