結果
問題 | No.1251 絶対に間違ってはいけない最小化問題 |
ユーザー |
![]() |
提出日時 | 2020-10-09 22:31:56 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 216 ms / 2,000 ms |
コード長 | 4,435 bytes |
コンパイル時間 | 2,413 ms |
コンパイル使用メモリ | 117,440 KB |
実行使用メモリ | 43,136 KB |
最終ジャッジ日時 | 2024-07-20 12:53:49 |
合計ジャッジ時間 | 16,882 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Globalization;using System.IO;using System.Linq;using System.Text;using System.Threading;// (づ°ω°)づミe★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜public class Solver{public void Solve(){int n = ReadInt();var a = ReadIntArray();var b = ReadIntArray();Array.Sort(a, b);long rsum = 0, rb = 0;for (int i = 1; i < n; i++){rsum += 1L * b[i] * (a[i] - a[0]);rb += b[i];}int best = 0;long ans = rsum;long lsum = 0, lb = 0;for (int i = 1; i < n; i++){rsum -= rb * (a[i] - a[i - 1]);rb -= b[i];lb += b[i - 1];lsum += lb * (a[i] - a[i - 1]);if (lsum + rsum < ans){ans = lsum + rsum;best = i;}}Write(a[best], ans);}#region Mainprotected static TextReader reader;protected static TextWriter writer;static void Main(){#if DEBUGreader = new StreamReader("..\\..\\input.txt");//reader = new StreamReader(Console.OpenStandardInput());writer = Console.Out;//writer = new StreamWriter("..\\..\\output.txt");#elsereader = new StreamReader(Console.OpenStandardInput());writer = new StreamWriter(Console.OpenStandardOutput());//reader = new StreamReader("input.txt");//writer = new StreamWriter("output.txt");#endiftry{new Solver().Solve();//var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);//thread.Start();//thread.Join();}catch (Exception ex){#if DEBUGConsole.WriteLine(ex);#elsethrow;#endif}reader.Close();writer.Close();}#endregion#region Read / Writeprivate static Queue<string> currentLineTokens = new Queue<string>();private static string[] ReadAndSplitLine() { return reader.ReadLine().Split(new[] { ' ', '\t', }, StringSplitOptions.RemoveEmptyEntries); }public static string ReadToken() { while (currentLineTokens.Count == 0) currentLineTokens = new Queue<string>(ReadAndSplitLine()); returncurrentLineTokens.Dequeue(); }public static int ReadInt() { return int.Parse(ReadToken()); }public static long ReadLong() { return long.Parse(ReadToken()); }public static double ReadDouble() { return double.Parse(ReadToken(), CultureInfo.InvariantCulture); }public static int[] ReadIntArray() { return ReadAndSplitLine().Select(int.Parse).ToArray(); }public static long[] ReadLongArray() { return ReadAndSplitLine().Select(long.Parse).ToArray(); }public static double[] ReadDoubleArray() { return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray(); }public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++)matrix[i] = ReadIntArray(); return matrix; }public static int[][] ReadAndTransposeIntMatrix(int numberOfRows){int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++) ret[i][j] = matrix[j][i]; }return ret;}public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++) lines[i] = reader.ReadLine().Trim(); return lines; }public static void WriteArray<T>(IEnumerable<T> array) { writer.WriteLine(string.Join(" ", array)); }public static void Write(params object[] array) { WriteArray(array); }public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array) writer.WriteLine(a); }private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>{public new TValue this[TKey key]{get { return ContainsKey(key) ? base[key] : default(TValue); }set { base[key] = value; }}}private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++) ret[i] = new T(); return ret; }#endregion}