Submission #46314486

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;

namespace Tasks;

public class D
{
    public static void Main()
    {
        using var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }

    public static void Solve()
    {
        var N = Scanner.Scan<int>();
        var dict = new Dictionary<long, long>();
        var queue = new PriorityQueue<long>();
        for (var i = 0; i < N; i++)
        {
            var (s, c) = Scanner.Scan<long, long>();
            if (!dict.ContainsKey(s)) dict[s] = 0;
            dict[s] += c;
            queue.Enqueue(s);
        }

        while (queue.Count > 0)
        {
            var s = queue.Dequeue();
            var c = dict[s];
            var ns = s * 2;
            var nc = c / 2;
            if (nc > 0)
            {
                if (!dict.ContainsKey(ns)) dict[ns] = 0;
                dict[ns] += nc;
                dict[s] -= nc * 2;
                queue.Enqueue(ns);
            }
        }

        var answer = dict.Values.Sum();
        Console.WriteLine(answer);
    }

    public class PriorityQueue<T> : IReadOnlyCollection<T>
    {
        private readonly Comparison<T> _comparison;
        private readonly List<T> _heap;
        public PriorityQueue(IEnumerable<T> items, IComparer<T> comparer = null) : this(comparer)
        {
            foreach (var item in items) Enqueue(item);
        }
        public PriorityQueue(IEnumerable<T> items, Comparison<T> comparison) : this(comparison)
        {
            foreach (var item in items) Enqueue(item);
        }
        public PriorityQueue(IComparer<T> comparer = null) : this((comparer ?? Comparer<T>.Default).Compare) { }
        public PriorityQueue(Comparison<T> comparison)
        {
            _heap = new List<T>();
            _comparison = comparison;
        }
        public int Count => _heap.Count;
        public IEnumerator<T> GetEnumerator() => _heap.GetEnumerator();
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        public void Enqueue(T item)
        {
            var child = Count;
            _heap.Add(item);
            while (child > 0)
            {
                var parent = (child - 1) / 2;
                if (_comparison(_heap[parent], _heap[child]) <= 0) break;
                (_heap[parent], _heap[child]) = (_heap[child], _heap[parent]);
                child = parent;
            }
        }
        public T Dequeue()
        {
            if (Count == 0) throw new InvalidOperationException();
            var result = _heap[0];
            _heap[0] = _heap[Count - 1];
            _heap.RemoveAt(Count - 1);
            var parent = 0;
            while (parent * 2 + 1 < Count)
            {
                var left = parent * 2 + 1;
                var right = parent * 2 + 2;
                if (right < Count && _comparison(_heap[left], _heap[right]) > 0)
                    left = right;
                if (_comparison(_heap[parent], _heap[left]) <= 0) break;
                (_heap[parent], _heap[left]) = (_heap[left], _heap[parent]);
                parent = left;
            }
            return result;
        }
        public T Peek()
        {
            if (Count == 0) throw new InvalidOperationException();
            return _heap[0];
        }
        public bool TryDequeue(out T result)
        {
            if (Count > 0)
            {
                result = Dequeue();
                return true;
            }
            result = default;
            return false;
        }
        public bool TryPeek(out T result)
        {
            if (Count > 0)
            {
                result = Peek();
                return true;
            }
            result = default;
            return false;
        }
        public void Clear() => _heap.Clear();
        public bool Contains(T item) => _heap.Contains(item);
    }

    public static class Scanner
    {
        public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
        public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
        {
            var input = ScanStringArray();
            return (Convert<T1>(input[0]), Convert<T2>(input[1]));
        }
        public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
        {
            var input = ScanStringArray();
            return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
        }
        public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
        {
            var input = ScanStringArray();
            return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
        }
        public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
        {
            var input = ScanStringArray();
            return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
        }
        public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
        {
            var input = ScanStringArray();
            return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
        }
        public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
        private static string[] ScanStringArray()
        {
            var line = Console.ReadLine()?.Trim() ?? string.Empty;
            return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
        }
        private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
    }
}

Submission Info

Judge Result