結果
問題 | No.1251 絶対に間違ってはいけない最小化問題 |
ユーザー |
|
提出日時 | 2020-10-09 21:45:30 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 1,489 ms / 2,000 ms |
コード長 | 1,886 bytes |
コンパイル時間 | 17,704 ms |
コンパイル使用メモリ | 459,736 KB |
実行使用メモリ | 110,104 KB |
最終ジャッジ日時 | 2024-07-20 10:28:34 |
合計ジャッジ時間 | 59,939 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
import java.io.BufferedReaderimport java.io.InputStreamimport java.io.InputStreamReaderimport java.io.PrintWriterimport java.util.*fun PrintWriter.solve(sc: FastScanner) {val n = sc.nextInt()val a = Array(n) { sc.nextLong() }val b = Array(n) { sc.nextLong() }val map = mutableMapOf<Long, Long>()for (i in 0 until n) {map[a[i]] = (map[a[i]] ?: 0) + b[i]}val sum = map.values.sum()var lsum = 0Lvar rsum = sumvar x1 = 0Lvar min1 = Long.MAX_VALUEfor (x in map.keys.sorted()) {rsum -= map[x]!!if (lsum >= rsum) {var ans = 0Lfor ((k, v) in map) {ans += v * Math.abs(x - k)}x1 = xmin1 = ansbreak}lsum += map[x]!!}lsum = sumrsum = 0Lvar x2 = 0Lvar min2 = Long.MAX_VALUEfor (x in map.keys.sortedDescending()) {lsum -= map[x]!!if (rsum >= lsum) {var ans = 0Lfor ((k, v) in map) {ans += v * Math.abs(x - k)}x2 = xmin2 = ansbreak}rsum += map[x]!!}if (min1 < min2) {println("$x1 $min1")} else {println("$x2 $min2")}}fun main() {val writer = PrintWriter(System.out, false)writer.solve(FastScanner(System.`in`))writer.flush()}class FastScanner(s: InputStream) {private var st = StringTokenizer("")private val br = BufferedReader(InputStreamReader(s))fun next(): String {while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())return st.nextToken()}fun nextInt() = next().toInt()fun nextLong() = next().toLong()fun nextLine() = br.readLine()fun nextDouble() = next().toDouble()fun ready() = br.ready()}