結果
| 問題 | No.506 限られたジャパリまん |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-15 14:03:15 |
| 言語 | C# (.NET 10.0.403 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 731 ms / 2,000 ms |
| + 843µs | |
| コード長 | 6,101 bytes |
| 記録 | |
| コンパイル時間 | 12,975 ms |
| コンパイル使用メモリ | 171,792 KB |
| 実行使用メモリ | 52,224 KB |
| 最終ジャッジ日時 | 2026-11-15 14:03:39 |
| 合計ジャッジ時間 | 19,526 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 25 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (205 ミリ秒)。 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 long NN => long.Parse(ReadLine());
static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var c = NList;
var (h, w, k, p) = (c[0] + 1, c[1] + 1, c[2], c[3]);
var fr = SList(k);
var map = new int[h, w];
for (var i = 0; i < h; ++i) for (var j = 0; j < w; ++j) map[i, j] = -1;
for (var i = 0; i < k; ++i)
{
var s = fr[i].Split();
map[int.Parse(s[0]), int.Parse(s[1])] = i;
}
var bitmax = 1 << k;
var ans = new HugeInt(6);
var maxb = 0;
for (var b = 0; b < bitmax; ++b)
{
if (Popcount(b) != p) continue;
var dp = new HugeInt[h, w];
for (var i = 0; i < h; ++i) for (var j = 0; j < w; ++j)
{
dp[i, j] = new HugeInt(6);
if (i == 0 && j == 0) dp[i, j] = HugeInt.Sum(dp[i, j], 1);
if (map[i, j] >= 0 && ((b >> map[i, j]) & 1) == 0) continue;
if (i > 0) dp[i, j] = HugeInt.Sum(dp[i, j], dp[i - 1, j]);
if (j > 0) dp[i, j] = HugeInt.Sum(dp[i, j], dp[i, j - 1]);
}
if (dp[h - 1, w - 1].IsLarge(ans))
{
ans = dp[h - 1, w - 1];
maxb = b;
}
}
WriteLine(HugeInt.Mod(ans, 1_000_000_007));
for (var i = 0; i < k; ++i) if (((maxb >> i) & 1) == 1) WriteLine(fr[i].Split()[2]);
}
/// <summary>
/// 10^27以上の大きい値どうしの計算をO(logN)で行う
/// </summary>
class HugeInt
{
static int div = 1 << 30;
public List<int> Digits;
public HugeInt(int length)
{
Digits = new List<int>(length);
for (var i = 0; i < length; ++i) Digits.Add(0);
}
public bool IsLarge(HugeInt b)
{
for (var i = Digits.Count - 1; i >= 0; --i)
{
if (Digits[i] > b.Digits[i]) return true;
if (Digits[i] < b.Digits[i]) return false;
}
return false;
}
public override string ToString()
{
var c = new List<char>(Digits.Count);
var flg = false;
for (var i = Digits.Count - 1; i >= 0; --i)
{
if (Digits[i] > 0) flg = true;
if (flg) c.Add((char)(Digits[i] + '0'));
}
if (c.Count == 0) c.Add('0');
return string.Concat(c);
}
public static HugeInt Sum(HugeInt a, int b)
{
var ans = new HugeInt(a.Digits.Count);
var add = (long)b;
for (var i = 0; i < a.Digits.Count; ++i)
{
var sum = a.Digits[i] + add;
if (sum > div)
{
ans.Digits[i] = (int)(sum - div);
add = 1;
}
else
{
ans.Digits[i] = (int)sum;
add = 0;
}
}
return ans;
}
// public static HugeInt Rem(HugeInt a, int b)
// {
// var ans = new HugeInt(a.Digits.Count);
// for (var i = 0; i < a.Digits.Count; ++i) ans.Digits[i] = a.Digits[i];
// ans.Digits[0] -= b;
// for (var i = 0; i < ans.Digits.Count; ++i)
// {
// if (ans.Digits[i] < 0)
// {
// var d = ans.Digits[i] / 10;
// ans.Digits[i] += d * 10;
// if (ans.Digits[i] < 0)
// {
// ++d;
// ans.Digits[i] += 10;
// }
// ans.Digits[i + 1] -= d;
// }
// }
// return ans;
// }
public static HugeInt Sum(HugeInt a, HugeInt b)
{
var ans = new HugeInt(a.Digits.Count);
var add = 0;
for (var i = 0; i < a.Digits.Count; ++i)
{
var sum = (long)a.Digits[i] + b.Digits[i] + add;
if (sum > div)
{
ans.Digits[i] = (int)(sum - div);
add = 1;
}
else
{
ans.Digits[i] = (int)sum;
add = 0;
}
}
return ans;
}
public static HugeInt Div(HugeInt a, int d)
{
var ans = new HugeInt(a.Digits.Count);
var rem = 0L;
for (var i = a.Digits.Count - 1; i >= 0; --i)
{
rem = rem * div + a.Digits[i];
ans.Digits[i] = (int)(rem / d);
rem = rem % d;
}
return ans;
}
public static long Mod(HugeInt a, long m)
{
var ans = 0L;
for (var i = a.Digits.Count - 1; i >= 0; --i)
{
ans = (ans * div + a.Digits[i]) % m;
}
return ans;
}
}
static int Popcount(long n)
{
var c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555);
c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333);
c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f);
c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff);
c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff);
c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff);
return (int)c;
}
}