結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー yk1095yk1095
提出日時 2020-07-03 14:59:38
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,838 bytes
コンパイル時間 1,816 ms
コンパイル使用メモリ 66,200 KB
実行使用メモリ 48,856 KB
最終ジャッジ日時 2023-10-14 23:31:16
合計ジャッジ時間 6,588 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
29,400 KB
testcase_01 AC 67 ms
24,972 KB
testcase_02 AC 67 ms
25,052 KB
testcase_03 AC 67 ms
22,988 KB
testcase_04 AC 68 ms
23,072 KB
testcase_05 AC 69 ms
22,996 KB
testcase_06 AC 68 ms
22,984 KB
testcase_07 AC 68 ms
22,952 KB
testcase_08 AC 68 ms
20,916 KB
testcase_09 AC 68 ms
22,972 KB
testcase_10 AC 67 ms
20,860 KB
testcase_11 AC 67 ms
22,860 KB
testcase_12 AC 68 ms
22,920 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます

ソースコード

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