#1195527 (C#) No.655 E869120 and Good Triangles

• 問題: No.655 E869120 and Good Triangles
• ユーザー: 👑 kakel-san
• 提出日時: 2026-10-27 00:10:15
• 言語: C# (.NET 10.0.402 + ACL)
• 結果: AC
• 実行時間: 1,460 ms / 2,500 ms
• コード長: 4,994 bytes
• コンパイル時間: 9,078 ms
• コンパイル使用メモリ: 171,248 KB
• 実行使用メモリ: 351,568 KB
• 最終ジャッジ日時: 2026-10-27 00:11:02
• 合計ジャッジ時間: 32,023 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 31

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (245 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

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

class Program
{
    static int NN => int.Parse(ReadLine());
    static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
    static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
    static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, k, p) = ((int)c[0], (int)c[1], c[2]);
        var map = NMap(k);
        WriteLine(Calc(n, k, p, map));
    }
    static long Calc(int n, int k, long p, int[][] map)
    {
        var INF = int.MaxValue / 2;
        var dp = new int[n][];
        for (var i = 0; i < n; ++i)
        {
            dp[i] = new int[i + 1];
            for (var j = 0; j <= i; ++j) dp[i][j] = INF;
        }
        var q = new Queue<(int x, int y)>();
        foreach (var pt in map)
        {
            dp[pt[0]][pt[1]] = 0;
            q.Enqueue((pt[0], pt[1]));
        }
        var mx = new int[] { -1, -1, 0, 0, 1, 1 };
        var my = new int[] { -1, 0, -1, 1, 0, 1 };
        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            for (var i = 0; i < mx.Length; ++i)
            {
                var nx = cur.x + mx[i];
                var ny = cur.y + my[i];
                if (nx < 0 || nx >= n || ny < 0 || ny > nx) continue;
                if (dp[nx][ny] <= dp[cur.x][cur.y] + 1) continue;
                dp[nx][ny] = dp[cur.x][cur.y] + 1;
                q.Enqueue((nx, ny));
            }
        }
        var c1 = new long[n]; // 右上
        var c2 = new long[n]; // 左上
        var c3 = new long[n]; // 下
        var c4 = new long[n, n]; // 上
        var c5 = new long[n, n]; // 左下
        var c6 = new long[n, n]; // 右下
        var all = 0L;
        for (var i = 0; i < n; ++i) for (var j = 0; j <= i; ++j)
        {
            c1[i - j] += dp[i][j];
            c2[j] += dp[i][j];
            c3[n - i - 1] += dp[i][j];
            all += dp[i][j];
        }
        for (var i = 1; i < n; ++i)
        {
            c1[i] += c1[i - 1];
            c2[i] += c2[i - 1];
            c3[i] += c3[i - 1];
        }
        for (var j = 0; j < n; ++j)
        {
            var sub = 0L;
            for (var i = j; i < n; ++i)
            {
                sub += dp[i][j];
                c4[i, j] = sub;
                if (j > 0) c4[i, j] += c4[i - 1, j - 1];
            }
        }
        for (var i = n - 1; i >= 0; --i)
        {
            var sub = 0L;
            for (var j = 0; j <= i; ++j)
            {
                sub += dp[i][j];
                c5[i, j] = sub;
                if (i < n - 1) c5[i, j] += c5[i + 1, j];
            }
        }
        for (var i = n - 1; i >= 0; --i)
        {
            var sub = 0L;
            for (var j = i; j >= 0; --j)
            {
                sub += dp[i][j];
                c6[i, j] = sub;
                if (i < n - 1) c6[i, j] += c6[i + 1, j + 1];
            }
        }
        var ans = 0L;
        for (var i = 0; i < n; ++i) for (var j = 0; j <= i; ++j)
        {
            if (dp[i][j] >= p)
            {
                ans += n - i;
            }
            else
            {
                var max = Calc(n, i, j, n - i - 1, all, c1, c2, c3, c4, c5, c6);
                if (max >= p)
                {
                    var ok = n - i - 1;
                    var ng = 0;
                    while (ok - ng > 1)
                    {
                        var mid = (ok + ng) / 2;
                        var tmp = Calc(n, i, j, mid, all, c1, c2, c3, c4, c5, c6);
                        if (tmp >= p) ok = mid;
                        else ng = mid;
                    }
                    ans += n - i - ok;
                }
            }
        }
        return ans;
    }
    static long Calc(int n, int i, int j, int len, long all, long[] c1, long[] c2, long[] c3, long[,] c4, long[,] c5, long[,] c6)
    {
        var dx = i + len;
        var ly = j;
        var ry = j + len;
        var ans = all;
        if (i > j)
        {
            ans -= c1[i - j - 1];
        }
        if (j > 0)
        {
            ans -= c2[j - 1];
        }
        if (dx + 1 < n)
        {
            ans -= c3[n - 2 - dx];
        }
        var x4 = i - 2;
        var y4 = j - 1;
        if (x4 >= 0 && y4 >= 0)
        {
            ans += c4[x4, y4];
        }
        var x5 = dx + 1;
        var y5 = ly - 1;
        if (x5 < n && y5 >= 0)
        {
            ans += c5[x5, y5];
        }
        var x6 = dx + 1;
        var y6 = ry + 2;
        if (x6 < n && y6 <= x6)
        {
            ans += c6[x6, y6];
        }
        return ans;
    }
}