[COCI 2022/2023 #5] Zastave

Luogu

IDLGP9181

Time1000ms

Memory512MB

DifficultyP6

2022Special JudgeCOCI（克罗地亚）

有 $n$ 个直角三角形，第 $i$ 个直角三角形的斜边长度为 $r_i$，这些直角三角形的高度和不超过 $S$。求这 $n$ 个直角三角形的最大面积和。 ## Input 第一行两个整数 $n,S\ (1\le n\le 10^5,1\le S\le 10^{10})$，表示三角形个数和这些三角形的高度之和的最大值。第二行 $n$ 个整数 $r_i\ (1\le r_i\le 10^5)$。 ## Output 输出这 $n$ 个直角三角形的最大面积和（保留 $10$ 位小数）。如果你的输出与答案的绝对误差或相对误差不超过 $10^{-6}$ 则认为你的输出正确。 [samples] ## Note 样例 $2$ 解释：最大可能的情况是这个三角形的三边长为 $6,8,10$，面积为 $24$。 |子任务编号| 附加限制| 分值| |:-:|:-:|:-:| |$0$| 是样例| $0$| |$1$| $n\le 100$| $37$| |$2$| $n\le 1000$| $20$| |$3$| 无附加限制| $43$|

Samples

Input #1

2 3
4 5

Output #1

6.5200982141

Input #2

1 6
10

Output #2

24.0000000000

Input #3

4 7
5 5 6 6

Output #3

18.5706715170

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #5] Zastave",
    "description": {
      "content": "有 $n$ 个直角三角形，第 $i$ 个直角三角形的斜边长度为 $r_i$，这些直角三角形的高度和不超过 $S$。求这 $n$ 个直角三角形的最大面积和。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9181"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个直角三角形，第 $i$ 个直角三角形的斜边长度为 $r_i$，这些直角三角形的高度和不超过 $S$。求这 $n$ 个直角三角形的最大面积和。\n\n## Input\n\n第一行两个整数 $n,S\\ (1\\le n\\le 10^5,1\\le S\\le 10^{10})$，表示三角形个数和这些三角形的高度之和的最大值。\n\n第二行 $n$ 个整数 $r_i\\ (1\\le r_i\\le 10^5)...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments