結果
問題 | No.1345 Beautiful BINGO |
ユーザー | keymoon |
提出日時 | 2021-01-17 01:03:35 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 828 ms / 2,000 ms |
コード長 | 2,424 bytes |
コンパイル時間 | 2,528 ms |
コンパイル使用メモリ | 113,324 KB |
実行使用メモリ | 31,636 KB |
最終ジャッジ日時 | 2024-11-28 16:36:02 |
合計ジャッジ時間 | 15,063 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Numerics; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using static System.Math; public static class P { public static void Main() { var nm = Console.ReadLine().Split().Select(int.Parse).ToArray(); var n = nm[0]; var m = nm[1]; var bingo = Enumerable.Repeat(0, n).Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()).ToArray(); static int Solve(int[][] bingo, int norma) { int res = int.MaxValue / 2; int n = bingo.Length; for (int b = 0; b < (1 << n); b++) { int[] cols = new int[n]; int popcnt = 0; for (int i = 0; i < n; i++) popcnt += b >> i & 1; if (popcnt + n < norma) continue; int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((b >> i & 1) != 1) cols[j] += bingo[i][j]; else sum += bingo[i][j]; } } sum += cols.OrderBy(x => x).Take(norma - popcnt).Sum(); res = Min(res, sum); } return res; } var res = Solve(bingo, m); { var newBingo1 = bingo.Select(x => x.ToArray()).ToArray(); var newBingo2 = bingo.Select(x => x.ToArray()).ToArray(); var newBingo3 = bingo.Select(x => x.ToArray()).ToArray(); int sum1 = 0; int sum2 = 0; int sum3 = 0; for (int i = 0; i < n; i++) { sum1 += newBingo1[i][i]; newBingo1[i][i] = 0; sum3 += newBingo3[i][i]; newBingo3[i][i] = 0; sum2 += newBingo2[i][n - i - 1]; newBingo2[i][n - i - 1] = 0; sum3 += newBingo3[i][n - i - 1]; newBingo3[i][n - i - 1] = 0; } res = Min(res, Solve(newBingo1, m - 1) + sum1); res = Min(res, Solve(newBingo2, m - 1) + sum2); if (1 < m) res = Min(res, Solve(newBingo3, m - 2) + sum3); } Console.WriteLine(res); } }