結果

問題 No.20 砂漠のオアシス
ユーザー ひばち
提出日時 2019-11-19 20:02:31
言語 C#
(csc 3.100.19.26603)
結果
WA   .
実行時間 -
コード長 7,784 Byte
コンパイル時間 1,810 ms
使用メモリ 13,328 KB
最終ジャッジ日時 2019-11-19 20:02:47

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 50 ms
10,764 KB
02.txt AC 51 ms
10,788 KB
03.txt AC 50 ms
10,792 KB
04.txt AC 58 ms
10,944 KB
05.txt AC 47 ms
10,920 KB
06.txt AC 80 ms
12,636 KB
07.txt AC 91 ms
13,324 KB
08.txt AC 86 ms
13,004 KB
09.txt AC 90 ms
13,328 KB
10.txt AC 87 ms
13,324 KB
99_challenge01.txt AC 44 ms
10,760 KB
99_challenge02.txt AC 42 ms
10,764 KB
system_test1.txt AC 47 ms
10,908 KB
system_test2.txt AC 45 ms
10,932 KB
system_test3.txt AC 49 ms
10,988 KB
system_test4.txt AC 46 ms
10,948 KB
system_test5.txt WA -
system_test6.txt WA -
system_test7.txt WA -
system_test8.txt AC 64 ms
11,256 KB
system_test9.txt WA -
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.3.1-beta4-19462-11 (66a912c9)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Runtime.CompilerServices;
using System.Text;
using static Template;
using static System.Console;
using static System.Convert;
using static System.Math;
using Pi = Pair<int, int>;
using Number = System.Int64;

class Solver
{
    Scanner sc = new Scanner();
    //
    public void Solve()
    {
        int N, V, ox, oy;
        sc.Make(out N, out V, out ox, out oy);
        if (ox == 0 && oy == 0)
            ox = oy = 1;
        var L = sc.ArrInt2D(N);
        ox--; oy--;
        var dist = Create(N, () => Create(N, () => int.MaxValue / 2));
        dist[ox][oy] = L[ox][oy];
        var pq = new PriorityQueue<P>((a, b) => a.cost - b.cost);
        pq.Enqueue(new P(L[ox][oy], ox, oy));
        while (pq.Any())
        {
            var p = pq.Dequeue();
            if (p.cost > dist[p.x][p.y]) continue;
            for (var i = 0; i < 4; i++)
            {
                int x = p.x + gh[i], y = p.y + gw[i];
                if (!Inside(x, y, N, N)) continue;
                if (chmin(ref dist[x][y], p.cost + L[x][y]))
                    pq.Enqueue(new P(dist[x][y], x, y));
            }
        }
        if (oy == 0 && ox == 0)
            Fail(dist[N - 1][N - 1] < V ? "YES" : "NO");
        if (dist[0][0] + dist[N - 1][N - 1] < V)
            Fail("YES");
        V -= dist[0][0];
        V *= 2;
        if (V <= dist[N - 1][N - 1]) Fail("NO");
        WriteLine("YES");
    }
    struct P
    {
        public int cost, x, y;
        public P(int c,int X,int Y)
        { cost = c;x = X;y = Y; }
    }

    int[] gh = new[] { 0, 0, 1, -1 }, gw = new[] { 1, -1, 0, 0 };
    public static bool Inside(int h, int w, int hh, int ww)
        => 0 <= h && h < hh && 0 <= w && w < ww;
}

public class PriorityQueue<T>
{
    private List<T> item = new List<T>();
    private Comparison<T> cmp;
    public int Count { get { return item.Count; } }
    public T Peek { get { return item[0]; } }
    public PriorityQueue() { cmp = Comparer<T>.Default.Compare; }

    public PriorityQueue(Comparison<T> comparison) { cmp = comparison; }

    public PriorityQueue(IComparer<T> comparer) { cmp = comparer.Compare; }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private int Parent(int i)
        => (i - 1) >> 1;
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private int Left(int i)
        => (i << 1) + 1;
    public T Enqueue(T val)
    {
        int i = item.Count;
        item.Add(val);
        while (i > 0)
        {
            int p = Parent(i);
            if (cmp(item[p], val) <= 0)
                break;
            item[i] = item[p];
            i = p;
        }
        item[i] = val;
        return val;
    }
    public T Dequeue()
    {
        var ret = item[0];
        var p = 0;
        var x = item[item.Count - 1];
        while (Left(p) < item.Count - 1)
        {
            var l = Left(p);
            if (l < item.Count - 2 && cmp(item[l + 1], item[l]) < 0) l++;
            if (cmp(item[l], x) >= 0)
                break;
            item[p] = item[l];
            p = l;
        }
        item[p] = x;
        item.RemoveAt(item.Count - 1);
        return ret;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool Any() => item.Count > 0;
}
#region Template
public class Template
{
    static void Main(string[] args)
    {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Solver().Solve();
        Console.Out.Flush();
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool chmin<T>(ref T num, T val) where T : IComparable<T>
    { if (num.CompareTo(val) == 1) { num = val; return true; } return false; }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool chmax<T>(ref T num, T val) where T : IComparable<T>
    { if (num.CompareTo(val) == -1) { num = val; return true; } return false; }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void swap<T>(ref T v1, ref T v2)
    { var t = v2; v2 = v1; v1 = t; }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static T[] Create<T>(int n, Func<T> f)
    {
        var rt = new T[n];
        for (var i = 0; i < rt.Length; ++i)
            rt[i] = f();
        return rt;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static T[] Create<T>(int n, Func<int, T> f)
    {
        var rt = new T[n];
        for (var i = 0; i < rt.Length; ++i)
            rt[i] = f(i);
        return rt;
    }
    public static void Fail<T>(T s) { Console.WriteLine(s); Console.Out.Close(); Environment.Exit(0); }
}

public class Scanner
{
    public string Str => ReadLine().Trim();
    public int Int => int.Parse(Str);
    public long Long => long.Parse(Str);
    public double Double => double.Parse(Str);
    public int[] ArrInt => Str.Split(' ').Select(int.Parse).ToArray();
    public long[] ArrLong => Str.Split(' ').Select(long.Parse).ToArray();
    public char[][] Grid(int n) => Create(n, () => Str.ToCharArray());
    public int[] ArrInt1D(int n) => Create(n, () => Int);
    public long[] ArrLong1D(int n) => Create(n, () => Long);
    public int[][] ArrInt2D(int n) => Create(n, () => ArrInt);
    public long[][] ArrLong2D(int n) => Create(n, () => ArrLong);
    public Pair<T1, T2> PairMake<T1, T2>() => new Pair<T1, T2>(Next<T1>(), Next<T2>());
    public Pair<T1, T2, T3> PairMake<T1, T2, T3>() => new Pair<T1, T2, T3>(Next<T1>(), Next<T2>(), Next<T3>());
    private Queue<string> q = new Queue<string>();
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public T Next<T>() { if (q.Count == 0) foreach (var item in Str.Split(' ')) q.Enqueue(item); return (T)Convert.ChangeType(q.Dequeue(), typeof(T)); }
    public void Make<T1>(out T1 v1) => v1 = Next<T1>();
    public void Make<T1, T2>(out T1 v1, out T2 v2) { v1 = Next<T1>(); v2 = Next<T2>(); }
    public void Make<T1, T2, T3>(out T1 v1, out T2 v2, out T3 v3) { Make(out v1, out v2); v3 = Next<T3>(); }
    public void Make<T1, T2, T3, T4>(out T1 v1, out T2 v2, out T3 v3, out T4 v4) { Make(out v1, out v2, out v3); v4 = Next<T4>(); }
    public void Make<T1, T2, T3, T4, T5>(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5) { Make(out v1, out v2, out v3, out v4); v5 = Next<T5>(); }
    public void Make<T1, T2, T3, T4, T5, T6>(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5, out T6 v6) { Make(out v1, out v2, out v3, out v4, out v5); v6 = Next<T6>(); }
}
public class Pair<T1, T2> : IComparable<Pair<T1, T2>>
{
    public T1 v1;
    public T2 v2;
    public Pair() { }
    public Pair(T1 v1, T2 v2)
    { this.v1 = v1; this.v2 = v2; }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int CompareTo(Pair<T1, T2> p)
    {
        var c = Comparer<T1>.Default.Compare(v1, p.v1);
        if (c == 0)
            c = Comparer<T2>.Default.Compare(v2, p.v2);
        return c;
    }
    public override string ToString()
        => $"{v1.ToString()} {v2.ToString()}";
    public void Deconstruct(out T1 a, out T2 b) { a = v1; b = v2; }
}

public class Pair<T1, T2, T3> : Pair<T1, T2>, IComparable<Pair<T1, T2, T3>>
{
    public T3 v3;
    public Pair() : base() { }
    public Pair(T1 v1, T2 v2, T3 v3) : base(v1, v2)
    { this.v3 = v3; }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int CompareTo(Pair<T1, T2, T3> p)
    {
        var c = base.CompareTo(p);
        if (c == 0)
            c = Comparer<T3>.Default.Compare(v3, p.v3);
        return c;
    }
    public override string ToString()
        => $"{base.ToString()} {v3.ToString()}";
    public void Deconstruct(out T1 a, out T2 b, out T3 c) { Deconstruct(out a, out b); c = v3; }
}
#endregion
0