結果

問題 No.421 しろくろチョコレート
ユーザー ひばちひばち
提出日時 2019-08-17 23:58:22
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 9,366 bytes
コンパイル時間 2,293 ms
コンパイル使用メモリ 121,036 KB
実行使用メモリ 27,584 KB
最終ジャッジ日時 2024-09-23 07:23:35
合計ジャッジ時間 6,115 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
25,456 KB
testcase_01 AC 37 ms
27,512 KB
testcase_02 AC 35 ms
27,340 KB
testcase_03 AC 33 ms
25,328 KB
testcase_04 AC 33 ms
27,400 KB
testcase_05 AC 34 ms
27,452 KB
testcase_06 AC 33 ms
25,584 KB
testcase_07 AC 36 ms
27,472 KB
testcase_08 AC 33 ms
25,328 KB
testcase_09 AC 34 ms
25,524 KB
testcase_10 AC 33 ms
27,324 KB
testcase_11 AC 36 ms
27,376 KB
testcase_12 AC 34 ms
25,328 KB
testcase_13 AC 34 ms
25,456 KB
testcase_14 AC 33 ms
25,388 KB
testcase_15 AC 34 ms
27,324 KB
testcase_16 AC 39 ms
25,264 KB
testcase_17 AC 39 ms
27,368 KB
testcase_18 AC 42 ms
25,332 KB
testcase_19 AC 34 ms
27,500 KB
testcase_20 AC 38 ms
27,368 KB
testcase_21 AC 38 ms
25,452 KB
testcase_22 AC 36 ms
25,296 KB
testcase_23 AC 34 ms
25,412 KB
testcase_24 AC 33 ms
27,236 KB
testcase_25 AC 34 ms
27,372 KB
testcase_26 AC 33 ms
25,524 KB
testcase_27 AC 34 ms
27,372 KB
testcase_28 AC 35 ms
25,352 KB
testcase_29 AC 35 ms
24,976 KB
testcase_30 AC 35 ms
27,400 KB
testcase_31 AC 46 ms
25,552 KB
testcase_32 AC 36 ms
25,480 KB
testcase_33 AC 36 ms
25,516 KB
testcase_34 AC 34 ms
27,256 KB
testcase_35 AC 34 ms
25,328 KB
testcase_36 AC 35 ms
25,552 KB
testcase_37 AC 39 ms
27,376 KB
testcase_38 AC 42 ms
27,372 KB
testcase_39 AC 35 ms
23,220 KB
testcase_40 AC 36 ms
25,136 KB
testcase_41 AC 35 ms
25,456 KB
testcase_42 AC 34 ms
25,412 KB
testcase_43 AC 35 ms
27,376 KB
testcase_44 AC 38 ms
25,328 KB
testcase_45 AC 35 ms
25,392 KB
testcase_46 AC 33 ms
25,280 KB
testcase_47 AC 35 ms
25,268 KB
testcase_48 AC 42 ms
25,208 KB
testcase_49 AC 35 ms
27,480 KB
testcase_50 AC 35 ms
25,296 KB
testcase_51 AC 39 ms
23,220 KB
testcase_52 AC 35 ms
23,604 KB
testcase_53 AC 34 ms
25,464 KB
testcase_54 AC 34 ms
25,072 KB
testcase_55 AC 34 ms
27,444 KB
testcase_56 AC 35 ms
27,444 KB
testcase_57 AC 33 ms
25,404 KB
testcase_58 AC 37 ms
25,204 KB
testcase_59 AC 39 ms
27,584 KB
testcase_60 AC 43 ms
25,324 KB
testcase_61 AC 40 ms
25,160 KB
testcase_62 AC 33 ms
27,448 KB
testcase_63 AC 33 ms
25,208 KB
testcase_64 AC 32 ms
25,316 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;
using System.Text;
class Program
{
    private static void chmin<T>(ref T num, T val) where T : IComparable<T>
        => num = num.CompareTo(val) == 1 ? val : num;
    private static void chmax<T>(ref T num, T val) where T : IComparable<T>
        => num = num.CompareTo(val) == -1 ? val : num;
    static void Main(string[] args)
    {
        var pr = new Program();
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        pr.Solve();
        Console.Out.Flush();
    }
    void Solve()
    {       
        int n, m;
        Input.Make(out n, out m);
        var grid = Input.grid(n);
        var gh = new[] { 0, 0, 1, -1 };
        var gw = new[] { 1, -1, 0, 0 };
        var f = new MaxFlow(n * m + 2);
        var ctw = 0;
        var ctb = 0;
        for (var i = 0; i < n; i++)
            for (var j = 0; j < m; j++)
                if (grid[i][j] != '.')
                {
                    if ((i + j) % 2 == 0) ctw++;
                    else { ctb++; continue; }
                    for(var k = 0; k < 4; k++)
                    {
                        var h = gh[k] + i;
                        var w = gw[k] + j;
                        if (!Inside(h, w, n, m)||grid[h][w]=='.') continue;
                        f.AddDirectedEdge(i * m + j, h * m + w, 1);
                    }
                }
        for(var i=0;i<n;i++)
            for(var j=0;j<m;j++)
                if (grid[i][j] != '.')
                {
                    if ((i + j) % 2 == 0)
                        f.AddDirectedEdge(n * m, i * m + j, 1);
                    else f.AddDirectedEdge(i * m + j, n * m + 1, 1);
                }
        var c = f.Execute(n * m, n * m + 1);
        ctw -= c;
        ctb -= c;
        WriteLine(100 * c + 10 * Min(ctw, ctb) + Abs(ctw - ctb));
    }

    public static bool Inside(int h, int w, int[] hw)
        => Inside(h, w, hw[0], hw[1]);
    public static bool Inside(int h, int w, int hh, int ww)
        => 0 <= h && h < hh && 0 <= w && w < ww;
}

public class Input
{
    public static string read => ReadLine().Trim();
    public static int[] ar => read.Split(' ').Select(int.Parse).ToArray();
    public static int num => ToInt32(read);
    public static long[] arL => read.Split(' ').Select(long.Parse).ToArray();
    public static long numL => ToInt64(read);
    public static T[] create<T>(int n, Func<int, T> f)
        => Enumerable.Repeat(0, n).Select(f).ToArray();
    public static char[][] grid(int h)
        => create(h, _ => read.ToCharArray());
    public static int[] ar1D(int n)
        => create(n, _ => num);
    public static long[] arL1D(int n)
        => create(n, _ => numL);
    public static string[] strs(int n)
        => create(n, _ => read);
    public static int[][] ar2D(int n)
        => create(n, _ => ar);
    public static long[][] arL2D(int n)
        => create(n, _ => arL);
    public static List<T>[] edge<T>(int n)
        => create(n, _ => new List<T>());
    public static T GetValue<T>(string g)
    {
        var t = typeof(T);
        if (t == typeof(int))
            return (T)(object)int.Parse(g);
        if (t == typeof(long))
            return (T)(object)long.Parse(g);
        if (t == typeof(string))
            return (T)(object)g;
        if (t == typeof(char))
            return (T)(object)char.Parse(g);
        if (t == typeof(double))
            return (T)(object)double.Parse(g);
        if (t == typeof(bool))
            return (T)(object)bool.Parse(g);
        return default(T);
    }
    public static void Make<T1, T2>(out T1 v1, out T2 v2)
    {
        v1 = Next<T1>();
        v2 = Next<T2>();
    }
    public static void Make<T1, T2, T3>(out T1 v1, out T2 v2, out T3 v3)
    {
        Make(out v1, out v2);
        v3 = Next<T3>();
    }
    public static 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 static 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 static 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>();
    }
    private static Queue<string> sc;
    public static T Next<T>(){ sc = sc ?? new Queue<string>(); if (sc.Count == 0) foreach (var item in read.Split(' ')) sc.Enqueue(item);return GetValue<T>(sc.Dequeue()); }
    public static void Next<T>(ref T val) => val = Next<T>(); 
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public const int MOD = 1000000007;
}

public class Pair<T1, T2> : IComparable<Pair<T1, T2>>
{
    public T1 v1 { get; set; }
    public T2 v2 { get; set; }
    public Pair() { v1 = Input.Next<T1>(); v2 = Input.Next<T2>(); }
    public Pair(T1 v1, T2 v2)
    { this.v1 = v1; this.v2 = v2; }

    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 override bool Equals(object obj)
        => this == (Pair<T1, T2>)obj;
    public override int GetHashCode()
        => v1.GetHashCode() ^ v2.GetHashCode();
    public static bool operator ==(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) == 0;
    public static bool operator !=(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) != 0;
    public static bool operator >(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) == 1;
    public static bool operator >=(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) != -1;
    public static bool operator <(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) == -1;
    public static bool operator <=(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) != 1;
}

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

    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 class MaxFlow
{
    readonly List<Edge>[] G;
    readonly int[] lv, iter;

    public MaxFlow(int V)
    {
        G = new List<Edge>[V];
        lv = new int[V];
        iter = new int[V];
        for (int i = 0; i < G.Length; i++)
            G[i] = new List<Edge>();
    }

    public void AddDirectedEdge(int from, int to, int cap)
        => addEdge(from, to, cap, 0);

    public void AddUndirectedEdge(int from, int to, int cap)
        => addEdge(from, to, cap, cap);

    void addEdge(int f, int t, int c1, int c2)
    {
        var a = new Edge(t, c1);
        var b = new Edge(f, c2);
        Edge.Link(a, b);
        G[f].Add(a);
        G[t].Add(b);
    }

    public int Execute(int src, int sink, int f = -1)
    {
        int flow = 0;
        if (f < 0) f = int.MaxValue;
        while (f > 0)
        {
            bfs(src);
            if (lv[sink] == 0) return flow;
            Array.Clear(iter, 0, iter.Length);
            int df;
            while ((df = dfs(src, sink, f)) > 0) { flow += df; f -= df; }
        }
        return flow;
    }

    void bfs(int s)
    {
        Array.Clear(lv, 0, lv.Length);
        var q = new Queue<int>();
        lv[s] = 1;
        q.Enqueue(s);
        while (q.Count > 0)
        {
            var v = q.Dequeue();
            foreach (var e in G[v])
                if (e.Cap > 0 && lv[e.To] == 0)
                {
                    lv[e.To] = lv[v] + 1;
                    q.Enqueue(e.To);
                }
        }

    }
    int dfs(int v, int t, int f)
    {
        if (v == t) return f;
        int ret = 0;
        for (; iter[v] < G[v].Count; iter[v]++)
        {
            var e = G[v][iter[v]];
            if (e.Cap <= 0 || lv[v] >= lv[e.To]) continue;
            int df = dfs(e.To, t, Math.Min(f, e.Cap));
            if (df <= 0) continue;
            e.Cap -= df;
            e.Rev.Cap += df;
            ret += df; f -= df;
            if (f == 0) break;
        }
        return ret;

    }
    class Edge
    {
        public static void Link(Edge e1, Edge e2)
        {
            e1.Rev = e2; e2.Rev = e1;
        }
        public int To { get; private set; }
        public Edge Rev { get; private set; }
        public int Cap { get; set; }
        public Edge(int t, int c)
        {
            To = t;
            Cap = c;
        }
        public override string ToString()
        {
            return string.Format("to: {0}, cap: {1}", To, Cap);
        }
    }
}
0