ABC144-E Gluttony

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 5");
            WillReturn.Add("4 2 1");
            WillReturn.Add("2 3 1");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 8");
            WillReturn.Add("4 2 1");
            WillReturn.Add("2 3 1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11 14");
            WillReturn.Add("3 1 4 1 5 9 2 6 5 3 5");
            WillReturn.Add("8 9 7 9 3 2 3 8 4 6 2");
            //12
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;

    static long[] mAArr;
    static long[] mFArr;
    static long UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mK = wkArr[1];

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mFArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        UB = mAArr.GetUpperBound(0);

        mAArr = mAArr.OrderByDescending(pX => pX).ToArray();
        mFArr = mFArr.OrderBy(pX => pX).ToArray();

        // 0が達成可能な場合
        if (CanAchieve(0)) {
            Console.WriteLine(0);
            return;
        }

        long L = 0;
        long R = long.MaxValue;

        while (L + 1 < R) {
            long Mid = R / 2;
            if (R < long.MaxValue) {
                Mid = (L + R) / 2;
            }

            if (CanAchieve(Mid)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        Console.WriteLine(R);
    }

    // X以下にできるかを返す
    static bool CanAchieve(long pX)
    {
        long RestK = mK;
        for (long I = UB; 0 <= I; I--) {
            long CurrScore = mAArr[I] * mFArr[I];
            if (CurrScore <= pX) continue;

            long Diff = CurrScore - pX;
            long NeedK = Diff / mFArr[I];
            if (Diff % mFArr[I] > 0) NeedK++;

            if (RestK < NeedK) return false;
            RestK -= NeedK;
        }
        return true;
    }
}

解説

二分法で解いてます。