fork download
copy 
  1. using static IO;
  2. public class IO
  3. {
  4. public static IO Cin = new();
  5. public static StreamReader reader = new(Console.OpenStandardInput());
  6. public static StreamWriter writer = new(Console.OpenStandardOutput());
  7. public static implicit operator string(IO _) => reader.ReadLine();
  8. public static implicit operator char[](IO _) => reader.ReadLine().ToArray();
  9. public static implicit operator int(IO _) => int.Parse(reader.ReadLine());
  10. public static implicit operator double(IO _) => double.Parse(reader.ReadLine());
  11. public static implicit operator string[](IO _) => reader.ReadLine().Split();
  12. public static implicit operator int[](IO _) => Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
  13. public void Deconstruct(out int a, out int b) { int[] r = Cin; (a, b) = (r[0], r[1]); }
  14. public void Deconstruct(out int a, out int b, out int c) { int[] r = Cin; (a, b, c) = (r[0], r[1], r[2]); }
  15. public static void Loop(int end, Action<int> action, int start = 0, in int add = 1) { for (; start < end; start += add) action(start); }
  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. {
  22.     public static void Coding()
  23.     {
  24.         for (int n, k; ((n, k) = Cin) != (0, 0);)
  25.         {
  26.             int[][] arr = new int[n][];
  27.             Loop(n, i => arr[i] = Cin);
  28.  
  29.             Dictionary<(int y, int x, int r), int> memo = new();
  30.             int dp(int y, int x, int remain)
  31.             {
  32.                 if (y < 0) return remain > 0 ? int.MinValue / 2 : 0;
  33.                 if (memo.TryGetValue((y, x, remain), out int ret)) return ret;
  34.  
  35.                 memo[(y, x, remain)] = ret = Math.Max(
  36.                     dp(y - 1, x, remain-1) + arr[y][x],
  37.                     dp(y - 1, x ^ 1, remain) + arr[y][x] + arr[y][x ^ 1]
  38.                 );
  39.                 return ret;
  40.             }
  41.  
  42.             Coutln = Math.Max(dp(n - 1, 0, k), dp(n - 1, 1, k));
  43.         }
  44.     }
  45. }
Success #stdin #stdout 0.07s 31044KB
comments (?)
stdin
copy 
10 5
7 8
4 9
3 7
5 9
7 2
10 3
0 10
3 2
6 3
7 9
0 0
stdout
copy 
102
https://ideone.com/0ntL8O
language:
C# (NET 6.0)
created:
10 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!