結果

問題 No.1029 JJOOII 3
コンテスト
ユーザー kakel-san
提出日時 2025-11-06 23:37:24
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,241 ms / 2,000 ms
コード長 3,867 bytes
コンパイル時間 8,240 ms
コンパイル使用メモリ 169,776 KB
実行使用メモリ 236,736 KB
最終ジャッジ日時 2025-11-06 23:37:57
合計ジャッジ時間 31,586 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (152 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, k) = (c[0], c[1]);
        var list = new (string s, int c)[n];
        for (var i = 0; i < n; ++i)
        {
            var s = ReadLine().Split();
            list[i] = (s[0], int.Parse(s[1]));
        }
        var INF = long.MaxValue / 2;
        var cost = new long[k * 3][];
        for (var i = 0; i < cost.Length; ++i)
        {
            cost[i] = new long[81];
            for (var j = 1; j < 81; ++j) cost[i][j] = INF;
        }
        var g = 3 * k;
        for (var i = 0; i < n; ++i)
        {
            var s = list[i].s;
            var ci = list[i].c;
            var jc = new int[s.Length + 1];
            var oc = new int[s.Length + 1];
            var ic = new int[s.Length + 1];
            for (var j = 0; j < s.Length; ++j)
            {
                jc[j + 1] = jc[j] + (s[j] == 'J' ? 1 : 0);
                oc[j + 1] = oc[j] + (s[j] == 'O' ? 1 : 0);
                ic[j + 1] = ic[j] + (s[j] == 'I' ? 1 : 0);
            }
            for (var j = 0; j < k; ++j)
            {
                var next = j + jc[^1];
                if (next >= k)
                {
                    var pos = LowerBound(0, k - j, jc);
                    var ocount = oc[^1] - oc[pos];
                    if (ocount >= k)
                    {
                        // J->I
                        var pos2 = LowerBound(0, k - oc[pos], oc);
                        var icount = Math.Min(k, ic[^1] - ic[pos2]);
                        cost[j][k * 2 + icount - j] = Math.Min(cost[j][k * 2 + icount - j], ci);
                    }
                    else
                    {
                        // J->O
                        cost[j][k + ocount - j] = Math.Min(cost[j][k + ocount - j], ci);
                    }
                }
                else
                {
                    cost[j][next - j] = Math.Min(cost[j][next - j], ci);
                }
            }
            for (var j = k; j < k * 2; ++j)
            {
                var next = j + oc[^1];
                if (next >= k * 2)
                {
                    // O->I
                    var pos = LowerBound(0, k * 2 - j, oc);
                    var icount = Math.Min(k, ic[^1] - ic[pos]);
                    cost[j][k * 2 + icount - j] = Math.Min(cost[j][k * 2 + icount - j], ci);
                }
                else
                {
                    cost[j][next - j] = Math.Min(cost[j][next - j], ci);
                }
            }
            for (var j = k * 2; j < g; ++j)
            {
                var next = Math.Min(g, j + ic[^1]);
                cost[j][next - j] = Math.Min(cost[j][next - j], ci);
            }
        }
        var dp = Enumerable.Repeat(INF, g + 1).ToArray();
        dp[0] = 0;
        for (var i = 0; i < g; ++i) for (var j = 1; j < 81; ++j) if (i + j <= g) dp[i + j] = Math.Min(dp[i + j], dp[i] + cost[i][j]);
        WriteLine(dp[g] == INF ? -1 : dp[g]);
    }
    static int LowerBound(int left, int min, IList<int> list)
    {
        if (list[left] >= min) return left;
        var ng = left;
        var ok = list.Count;
        while (ok - ng > 1)
        {
            var mid = (ng + ok) / 2;
            if (list[mid] < min) ng = mid;
            else ok = mid;
        }
        return ok;
    }
}
0