結果
| 問題 | No.506 限られたジャパリまん |
| ユーザー |
 14番
|
| 提出日時 | 2017-04-24 16:56:52 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,547 bytes |
| コンパイル時間 | 2,410 ms |
| コンパイル使用メモリ | 109,532 KB |
| 実行使用メモリ | 23,932 KB |
| 最終ジャッジ日時 | 2023-09-10 12:53:58 |
| 合計ジャッジ時間 | 6,453 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 66 ms
19,836 KB |
| testcase_01 | AC | 67 ms
23,804 KB |
| testcase_02 | AC | 68 ms
21,704 KB |
| testcase_03 | AC | 66 ms
23,932 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Text;
public class Program
{
public void Proc() {
Reader.IsDebug = false;
int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
int h = inpt[1];
int w = inpt[0];
int fCount = inpt[2];
int jCount = inpt[3];
for(int i=0; i<fCount; i++) {
this.FrList.Add(new Fr(i, Reader.ReadLine()));
}
long[,] map = new long[w+1,h+1];
for(int x=0; x<=w; x++) {
for(int y=0; y<=h; y++) {
if(this.FrList.Any(a=>a.X == x && a.Y == y)) {
map[x,y] = 0;
} else if(x == 0 && y==0) {
map[0,0] = 1;
} else {
long tmp = 0;
if(x>0) {
tmp+=map[x-1,y];
}
if(y>0) {
tmp+=map[x,y-1];
}
map[x,y] = tmp;
}
}
}
Ans ans = GetAns(0,map, jCount);
Console.WriteLine(ans.WayCount);
for(int i=0; i<this.FrList.Count; i++) {
if(((1<<i)&ans.Flag)>0) {
Console.WriteLine(FrList[i].Name);
}
}
}
private struct Ans {
public long WayCount;
public int Flag;
public Ans(long w, int f) {
this.WayCount = w;
this.Flag = f;
}
}
private Ans GetAns(int flag, long[,] map, int remain) {
if(dic.ContainsKey(flag)) {
return dic[flag];
}
if(remain <= 0) {
return new Ans(map[map.GetLength(0)-1, map.GetLength(1)-1], flag);
}
Ans ans = new Ans(0,0);
for(int i=0; i<FrList.Count; i++) {
int key = 1<<i;
if(FrList[i].Kaitsu(map) == 0) {
continue;
}
if((flag&key)>0) {
continue;
}
long[,] subMap = new long[map.GetLength(0), map.GetLength(1)];
subMap[FrList[i].X, FrList[i].Y] = FrList[i].Kaitsu(map);
for(int x=0; x<map.GetLength(0); x++) {
for(int y=0; y<map.GetLength(1);y++) {
if(map[x,y] == 0) {
if(this.FrList.Any(a=>a.X == x&&a.Y==y)) {
int k = 1<<this.FrList.Find(a=>a.X == x && a.Y == y).ID;
if(k!=key && (flag&k)==0) {
continue;
}
}
}
if(x==0&&y==0) {
subMap[0,0] = map[0,0];
} else {
long tmp = 0;
if(x>0) {
tmp+=subMap[x-1,y];
}
if(y>0) {
tmp+=subMap[x,y-1];
}
subMap[x,y] = tmp;
}
}
}
Ans ret = GetAns(flag+key, subMap, remain-1);
if(ret.WayCount > ans.WayCount) {
ans = ret;
}
}
dic[flag] = ans;
return ans;
}
private List<Fr> FrList = new List<Fr>();
private const long ModNum = 1000000000 + 1;
private Dictionary<int, Ans> dic = new Dictionary<int, Ans>();
private class Fr {
public int X;
public int Y;
public int ID;
public String Name;
public long Kaitsu(long[,] mp) {
long ret = 0;
if(this.X == 0 && this.Y == 0) {
return 1;
}
if(this.X > 0) {
ret = mp[this.X-1, this.Y];
}
if(this.Y > 0) {
ret += mp[this.X, this.Y-1];
}
return ret;
}
public Fr(int id, String init) {
string[] spl = init.Split(' ');
this.ID = id;
this.X = int.Parse(spl[0]);
this.Y = int.Parse(spl[1]);
this.Name = spl[2];
}
}
public class Reader {
public static bool IsDebug = true;
private static System.IO.StringReader SReader;
private static string InitText = @"
3 4 2 0
3 3 konoha
2 4 mimi
";
public static string ReadLine() {
if(IsDebug) {
if(SReader == null) {
SReader = new System.IO.StringReader(InitText.Trim());
}
return SReader.ReadLine();
} else {
return Console.ReadLine();
}
}
}
public static void Main(string[] args)
{
Program prg = new Program();
prg.Proc();
}
}