結果
問題 | 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.BufferedReader import java.io.InputStream import java.io.InputStreamReader import java.io.PrintWriter import 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 = 0L var rsum = sum var x1 = 0L var min1 = Long.MAX_VALUE for (x in map.keys.sorted()) { rsum -= map[x]!! if (lsum >= rsum) { var ans = 0L for ((k, v) in map) { ans += v * Math.abs(x - k) } x1 = x min1 = ans break } lsum += map[x]!! } lsum = sum rsum = 0L var x2 = 0L var min2 = Long.MAX_VALUE for (x in map.keys.sortedDescending()) { lsum -= map[x]!! if (rsum >= lsum) { var ans = 0L for ((k, v) in map) { ans += v * Math.abs(x - k) } x2 = x min2 = ans break } 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() }