結果

問題 No.1095 Smallest Kadomatsu Subsequence
コンテスト
ユーザー yk1095
提出日時 2020-07-03 14:59:38
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,838 bytes
コンパイル時間 1,067 ms
コンパイル使用メモリ 113,788 KB
実行使用メモリ 59,396 KB
最終ジャッジ日時 2024-09-16 17:02:43
合計ジャッジ時間 5,662 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = (int)ReadLong();
            var A = ReadLongs();

            var lowerMinLeftForAt = new long[N];
            lowerMinLeftForAt[0] = long.MaxValue;
            var upperMinLeftForAt = new long[N];
            var sortedFromLeft = new SortedSet<long>
            {
                A[0],
            };
            for (var i = 1; i < N; i++)
            {
                lowerMinLeftForAt[i] = Math.Min(lowerMinLeftForAt[i - 1], A[i - 1]);

                if (A[i] < sortedFromLeft.Max)
                {
                    var sorted = sortedFromLeft.ToList();
                    var index = GetLowerBoundIndex(A[i], sorted);
                    upperMinLeftForAt[i] = sorted[(int)index];
                }
                else
                {
                    upperMinLeftForAt[i] = long.MaxValue;
                }
                // 次の判定用に追加
                sortedFromLeft.Add(A[i]);
            }

            var lowerMinRightForAt = new long[N];
            lowerMinRightForAt[N - 1] = long.MaxValue;
            var upperMinRightForAt = new long[N];
            var sortedFromRight = new SortedSet<long>
            {
                A[N - 1],
            };
            for (var i = N - 2; i >= 0; i--)
            {
                lowerMinRightForAt[i] = Math.Min(lowerMinRightForAt[i + 1], A[i + 1]);

                if (A[i] < sortedFromRight.Max)
                {
                    var sorted = sortedFromRight.ToList();
                    var index = GetLowerBoundIndex(A[i], sorted);
                    upperMinRightForAt[i] = sorted[(int)index];
                }
                else
                {
                    upperMinRightForAt[i] = long.MaxValue;
                }
                sortedFromRight.Add(A[i]);
            }

            var min = long.MaxValue;
            for (var i = 1; i < N - 1; i++)
            {
                var b = A[i];

                if (lowerMinLeftForAt[i] != long.MaxValue && lowerMinRightForAt[i] != long.MaxValue
                    && b > lowerMinLeftForAt[i] && b > lowerMinRightForAt[i])
                {
                    min = Math.Min(min, lowerMinLeftForAt[i] + b + lowerMinRightForAt[i]);
                }
                if (upperMinLeftForAt[i] != long.MaxValue && upperMinRightForAt[i] != long.MaxValue
                    && b < upperMinLeftForAt[i] && b < upperMinRightForAt[i])
                {
                    min = Math.Min(min, upperMinLeftForAt[i] + b + upperMinRightForAt[i]);
                }
            }

            return min == long.MaxValue ? -1 : min;
        }

        private static long GetLowerBoundIndex(long bound, IList<long> collection)
        {
            var l = 0;
            var r = collection.Count - 1;
            while (l <= r)
            {
                var mid = l + (r - l) / 2;
                if (bound > collection[mid])
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }

            return l;
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}
0