{"problem":{"name":"Max Dot","description":{"content":"Given are integers $N$, $M$, $S$, and a sequence of $N$ integers $A=(A_1,A_2,\\cdots,A_N)$. Consider making a sequence of $N$ non-negative **real** numbers $x=(x_1,x_2,\\cdots,x_N)$ satisfying all of th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc128_c"},"statements":[{"statement_type":"Markdown","content":"Given are integers $N$, $M$, $S$, and a sequence of $N$ integers $A=(A_1,A_2,\\cdots,A_N)$.\nConsider making a sequence of $N$ non-negative **real** numbers $x=(x_1,x_2,\\cdots,x_N)$ satisfying all of the following conditions:\n\n*   $0 \\leq x_1 \\leq x_2 \\leq \\cdots \\leq x_N \\leq M$,\n*   $\\sum_{1 \\leq i \\leq N} x_i=S$.\n\nNow, let us define the score of $x$ as $\\sum_{1 \\leq i \\leq N} A_i \\times x_i$. Find the maximum possible score of $x$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $1 \\leq M \\leq 10^6$\n*   $1 \\leq S \\leq \\min(N \\times M,10^6)$\n*   $1 \\leq A_i \\leq 10^6$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $S$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc128_c","tags":[],"sample_group":[["3 2 3\n1 2 3","8.00000000000000000000\n\nThe optimal choice is $x=(0,1,2)$."],["3 3 2\n5 1 1","4.66666666666666666667\n\nThe optimal choice is $x=(2/3,2/3,2/3)$."],["10 234567 1000000\n353239 53676 45485 617014 886590 423581 172670 928532 312338 981241","676780145098.25000000000000000000"]],"created_at":"2026-03-03 11:01:14"}}