fork download
copy 
  1. using static IO;
  2. public class IO {
  3. public static IO Cin = new();
  4. public static StreamReader reader = new(Console.OpenStandardInput());
  5. public static StreamWriter writer = new(Console.OpenStandardOutput());
  6. public static implicit operator string(IO _) => reader.ReadLine();
  7. public static implicit operator char[](IO _) => reader.ReadLine().ToArray();
  8. public static implicit operator int(IO _) => int.Parse(reader.ReadLine());
  9. public static implicit operator double(IO _) => double.Parse(reader.ReadLine());
  10. public static implicit operator string[](IO _) => reader.ReadLine().Split();
  11. public static implicit operator int[](IO _) => Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
  12. public void Deconstruct(out int a, out int b) { int[] r = Cin; (a, b) = (r[0], r[1]); }
  13. public void Deconstruct(out int a, out int b, out int c) { int[] r = Cin; (a, b, c) = (r[0], r[1], r[2]); }
  14. public static IEnumerable<int> MakeRange(int start, int count) => Enumerable.Range(start, count);
  15. public static T[] MakeArray<T>(int count) where T : new() => MakeRange(0, count).Select(_ => new T()).ToArray();
  16. public static object? Cout { set { writer.Write(value); } }
  17. public static object? Coutln { set { writer.WriteLine(value); } }
  18. public static void Main() { Program.Coding(); writer.Flush(); }
  19. }
  20. class Program {
  21.     record struct Point(ushort X, ushort Y) {
  22.         public readonly int GetIndex(int n) => Y * n + X;
  23.     }
  24.     public static void Coding() {
  25.         checked {
  26.             (int n, int blind) = Cin;
  27.  
  28.             int source = n * n;
  29.             int limiter = source + 1;
  30.             int sink = limiter + 1;
  31.  
  32.             int[][] eggs = MakeRange(0, n).Select(_ => (int[])Cin).ToArray();
  33.             PriorityQueue<(Point a, Point b), int> candidate = new();
  34.  
  35.             for (ushort y = 0; y < n; y++) {
  36.                 for (ushort x = 1; x < n; x++) {
  37.                     candidate.Enqueue((new((ushort)(x - 1), y), new(x, y)), eggs[y][x - 1] + eggs[y][x]);
  38.                     if (candidate.Count > 64) candidate.Dequeue();
  39.                 }
  40.             }
  41.             for (ushort x = 0; x < n; x++) {
  42.                 for (ushort y = 1; y < n; y++) {
  43.                     candidate.Enqueue((new(x, (ushort)(y - 1)), new(x, y)), eggs[y - 1][x] + eggs[y][x]);
  44.                     if (candidate.Count > 64) candidate.Dequeue();
  45.                 }
  46.             }
  47.  
  48.             FlowGraph graph = new(sink + 1);
  49.             HashSet<int> used = new();
  50.             while (candidate.Count > 0) {
  51.                 var (a, b) = candidate.Dequeue();
  52.                 if ((a.X + a.Y) % 2 is not 0) (a, b) = (b, a);
  53.  
  54.                 int ai = a.GetIndex(n);
  55.                 int bi = b.GetIndex(n);
  56.                 graph.AddLine(ai, bi, 1, 0);
  57.                 used.Add(ai);
  58.                 used.Add(bi);
  59.             }
  60.  
  61.             long sum = 0;
  62.             for (int y = 0; y < n; y++) {
  63.                 for (int x = 0; x < n; x++) {
  64.                     int unfresh = eggs[y][x];
  65.                     sum += unfresh;
  66.  
  67.                     int me = y * n + x;
  68.                     if (used.Contains(me) is false) continue;
  69.                     if ((x + y) % 2 is 0) {
  70.                         graph.AddLine(limiter, me, 1, -unfresh);
  71.                     }
  72.                     else {
  73.                         graph.AddLine(me, sink, 1, -unfresh);
  74.                     }
  75.                 }
  76.             }
  77.  
  78.             graph.AddLine(source, limiter, blind, 0);
  79.             _ = graph.GetMaxFlow(source, sink, out int cost);
  80.             Cout = sum + cost;
  81.         }
  82.     }
  83. }
  84. class FlowLine {
  85.     public int Start { get; }
  86.     public int End { get; }
  87.     public int Capacity { get; }
  88.     public int Flow { get; set; } = 0;
  89.     public FlowLine Reverse { get; }
  90.     public int Remaining => Capacity - Flow;
  91.     public int Cost { get; }
  92.     public FlowLine(int start, int end, int capacity, int cost, FlowLine? reverse = null) {
  93.         this.Start = start;
  94.         this.End = end;
  95.         this.Capacity = capacity;
  96.         this.Cost = cost;
  97.         this.Reverse = reverse ?? new(end, start, 0, -cost, this);
  98.     }
  99. }
  100. class FlowGraph {
  101.     public FlowGraph(int size) {
  102.         graph = MakeArray<List<FlowLine>>(Count = size);
  103.     }
  104.     public void AddLine(int start, int end, int capacity, int cost) {
  105.         FlowLine line = new(start, end, capacity, cost);
  106.         graph[start].Add(line);
  107.         graph[end].Add(line.Reverse);
  108.     }
  109.     public int GetMaxFlow(int source, int sink, out int cost) {
  110.         int totalFlow = 0;
  111.         for (cost = 0; true;) {
  112.             FlowLine?[] path = new FlowLine?[Count];
  113.             int[] dist = Enumerable.Repeat(int.MaxValue, Count).ToArray();
  114.             bool[] inQueue = new bool[Count];
  115.             Queue<int> queue = new();
  116.             dist[source] = 0;
  117.             inQueue[source] = true;
  118.             queue.Enqueue(source);
  119.             while (queue.Count > 0) {
  120.                 int node = queue.Dequeue();
  121.                 inQueue[node] = false;
  122.                 foreach (var line in graph[node]) {
  123.                     int nextdist = dist[node] + line.Cost;
  124.                     if (line.Remaining > 0 && dist[line.End] > nextdist) {
  125.                         dist[line.End] = nextdist;
  126.                         path[line.End] = line;
  127.                         if (inQueue[line.End] is false) {
  128.                             inQueue[line.End] = true;
  129.                             queue.Enqueue(line.End);
  130.                         }
  131.                     }
  132.                 }
  133.             }
  134.             if (path[sink] is not FlowLine sinkLine) break;
  135.             int flow = int.MaxValue;
  136.             for (FlowLine? line = sinkLine; line is not null; line = path[line.Start]) {
  137.                 flow = Math.Min(flow, line.Remaining);
  138.             }
  139.             for (FlowLine? line = sinkLine; line is not null; line = path[line.Start]) {
  140.                 line.Flow += flow;
  141.                 line.Reverse.Flow -= flow;
  142.                 cost += flow * line.Cost;
  143.             }
  144.             totalFlow += flow;
  145.         }
  146.         return totalFlow;
  147.     }
  148.     public int Count { get; }
  149.     private readonly List<FlowLine>[] graph;
  150. }
Success #stdin #stdout 0.08s 31624KB
comments (?)
stdin
copy 
3 1
2 7 6
9 5 1
4 3 8
stdout
copy 
31
https://ideone.com/xbMroT
31
language:
C# (NET 6.0)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!