Submission #5900821
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; using System.IO; using SB = System.Text.StringBuilder; //using System.Threading.Tasks; //using System.Text.RegularExpressions; //using System.Globalization; //using System.Diagnostics; using static System.Console; using System.Numerics; using static System.Math; using pair = Pair<int, int>; class Program { static void Main() { //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false }); new Program().solve(); Out.Flush(); } readonly Scanner cin = new Scanner(); readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑ readonly int mod = 1000000007; readonly int dom = 998244353; bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; } bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; } int[] Y; int[] X; long[,,,] dp; long calc(int sy, int ty, int sx, int tx) { if (ty <= sy || tx <= sx) { return 0; } var ret = dp[sy, ty, sx, tx]; if (ret >= 0) { return ret; } ret = 0; int N = Y.Length; for (int i = 0; i < N; i++) { if (sy <= Y[i] && Y[i] < ty && sx <= X[i] && X[i] < tx) { long sum = ty - sy + tx - sx - 1; sum += calc(sy, Y[i], sx, X[i]); sum += calc(sy, Y[i], X[i] + 1, tx); sum += calc(Y[i] + 1, ty, sx, X[i]); sum += calc(Y[i] + 1, ty, X[i] + 1, tx); chmax(ref ret, sum); } } return dp[sy, ty, sx, tx] = ret; } void solve() { int W = cin.nextint; int H = cin.nextint; int N = cin.nextint; if (W > 80 || H > 80) { throw new NotImplementedException(); } X = new int[N]; Y = new int[N]; for (int i = 0; i < N; i++) { X[i] = cin.nextint - 1; Y[i] = cin.nextint - 1; } dp = new long[H, H + 1, W, W + 1]; for (int i = 0; i < H; i++) { for (int j = 0; j < H + 1; j++) { for (int k = 0; k < W; k++) { for (int l = 0; l < W + 1; l++) { dp[i, j, k, l] = -1; } } } } var ans = calc(0, H, 0, W); WriteLine(ans); } } static class Ex { public static void join<T>(this IEnumerable<T> values, string sep = " ") => WriteLine(string.Join(sep, values)); public static string concat<T>(this IEnumerable<T> values) => string.Concat(values); public static string reverse(this string s) { var t = s.ToCharArray(); Array.Reverse(t); return t.concat(); } public static int lower_bound<T>(this IList<T> arr, T val) where T : IComparable<T> { int low = 0, high = arr.Count; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (arr[mid].CompareTo(val) < 0) low = mid + 1; else high = mid; } return low; } public static int upper_bound<T>(this IList<T> arr, T val) where T : IComparable<T> { int low = 0, high = arr.Count; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (arr[mid].CompareTo(val) <= 0) low = mid + 1; else high = mid; } return low; } } class Pair<T, U> : IComparable<Pair<T, U>> where T : IComparable<T> where U : IComparable<U> { public T f; public U s; public Pair(T f, U s) { this.f = f; this.s = s; } public int CompareTo(Pair<T, U> a) => f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s); public override string ToString() => $"{f} {s}"; } class Scanner { string[] s; int i; readonly char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string[] scan => ReadLine().Split(); public int[] scanint => Array.ConvertAll(scan, int.Parse); public long[] scanlong => Array.ConvertAll(scan, long.Parse); public double[] scandouble => Array.ConvertAll(scan, double.Parse); public string next { get { if (i < s.Length) return s[i++]; string st = ReadLine(); while (st == "") st = ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); i = 0; return next; } } public int nextint => int.Parse(next); public long nextlong => long.Parse(next); public double nextdouble => double.Parse(next); }
Submission Info
Submission Time | |
---|---|
Task | D - 金塊ゲーム |
User | claw88 |
Language | C# (Mono 4.6.2.0) |
Score | 99 |
Code Size | 5023 Byte |
Status | RE |
Exec Time | 553 ms |
Memory | 338912 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 80 / 80 | 19 / 19 | 0 / 1 | ||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt |
Subtask2 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt |
Subtask3 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt, subtask3_15.txt, subtask3_16.txt, subtask3_17.txt, subtask3_18.txt, subtask3_19.txt, subtask3_20.txt, subtask3_21.txt, subtask3_22.txt, subtask3_23.txt, subtask3_24.txt, subtask3_25.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 21 ms | 9172 KB |
sample_02.txt | AC | 21 ms | 9172 KB |
sample_03.txt | AC | 22 ms | 9084 KB |
subtask1_01.txt | AC | 21 ms | 9144 KB |
subtask1_02.txt | AC | 25 ms | 12896 KB |
subtask1_03.txt | AC | 21 ms | 9100 KB |
subtask1_04.txt | AC | 25 ms | 13152 KB |
subtask1_05.txt | AC | 52 ms | 31968 KB |
subtask1_06.txt | AC | 21 ms | 11220 KB |
subtask1_07.txt | AC | 25 ms | 13280 KB |
subtask1_08.txt | AC | 21 ms | 11220 KB |
subtask1_09.txt | AC | 547 ms | 336864 KB |
subtask1_10.txt | AC | 488 ms | 338912 KB |
subtask1_11.txt | AC | 487 ms | 337236 KB |
subtask1_12.txt | AC | 21 ms | 9200 KB |
subtask1_13.txt | AC | 27 ms | 14560 KB |
subtask1_14.txt | AC | 485 ms | 336864 KB |
subtask1_15.txt | AC | 488 ms | 338912 KB |
subtask1_16.txt | AC | 31 ms | 17376 KB |
subtask1_17.txt | AC | 38 ms | 22368 KB |
subtask1_18.txt | AC | 22 ms | 9184 KB |
subtask1_19.txt | AC | 21 ms | 9120 KB |
subtask1_20.txt | AC | 22 ms | 11168 KB |
subtask1_21.txt | AC | 52 ms | 29920 KB |
subtask1_22.txt | AC | 69 ms | 43872 KB |
subtask1_23.txt | AC | 22 ms | 11616 KB |
subtask1_24.txt | AC | 353 ms | 244064 KB |
subtask1_25.txt | AC | 484 ms | 336864 KB |
subtask2_01.txt | AC | 26 ms | 11872 KB |
subtask2_02.txt | AC | 25 ms | 13536 KB |
subtask2_03.txt | AC | 64 ms | 38240 KB |
subtask2_04.txt | AC | 553 ms | 338912 KB |
subtask2_05.txt | AC | 202 ms | 135648 KB |
subtask2_06.txt | AC | 96 ms | 59616 KB |
subtask2_07.txt | AC | 45 ms | 26336 KB |
subtask2_08.txt | AC | 42 ms | 21984 KB |
subtask2_09.txt | AC | 181 ms | 118368 KB |
subtask2_10.txt | AC | 456 ms | 312928 KB |
subtask2_11.txt | AC | 64 ms | 37600 KB |
subtask2_12.txt | AC | 445 ms | 307424 KB |
subtask2_13.txt | AC | 490 ms | 336992 KB |
subtask2_14.txt | AC | 488 ms | 336864 KB |
subtask2_15.txt | AC | 487 ms | 336864 KB |
subtask2_16.txt | AC | 54 ms | 31968 KB |
subtask2_17.txt | AC | 55 ms | 29920 KB |
subtask2_18.txt | AC | 208 ms | 140000 KB |
subtask2_19.txt | AC | 143 ms | 91872 KB |
subtask2_20.txt | AC | 174 ms | 115552 KB |
subtask2_21.txt | AC | 175 ms | 115552 KB |
subtask2_22.txt | AC | 299 ms | 201824 KB |
subtask2_23.txt | AC | 299 ms | 203872 KB |
subtask2_24.txt | AC | 489 ms | 337236 KB |
subtask2_25.txt | AC | 489 ms | 336992 KB |
subtask3_01.txt | RE | 20 ms | 10720 KB |
subtask3_02.txt | RE | 20 ms | 10720 KB |
subtask3_03.txt | RE | 20 ms | 12640 KB |
subtask3_04.txt | RE | 19 ms | 8672 KB |
subtask3_05.txt | RE | 19 ms | 10720 KB |
subtask3_06.txt | RE | 20 ms | 10592 KB |
subtask3_07.txt | RE | 20 ms | 10720 KB |
subtask3_08.txt | RE | 20 ms | 12768 KB |
subtask3_09.txt | RE | 19 ms | 10720 KB |
subtask3_10.txt | RE | 19 ms | 8672 KB |
subtask3_11.txt | RE | 19 ms | 10720 KB |
subtask3_12.txt | RE | 20 ms | 10720 KB |
subtask3_13.txt | RE | 19 ms | 10592 KB |
subtask3_14.txt | RE | 20 ms | 10720 KB |
subtask3_15.txt | RE | 19 ms | 10720 KB |
subtask3_16.txt | RE | 20 ms | 12640 KB |
subtask3_17.txt | RE | 19 ms | 10720 KB |
subtask3_18.txt | RE | 19 ms | 8672 KB |
subtask3_19.txt | RE | 20 ms | 12768 KB |
subtask3_20.txt | RE | 19 ms | 10592 KB |
subtask3_21.txt | RE | 19 ms | 10720 KB |
subtask3_22.txt | RE | 20 ms | 10720 KB |
subtask3_23.txt | RE | 19 ms | 8544 KB |
subtask3_24.txt | RE | 19 ms | 8672 KB |
subtask3_25.txt | RE | 20 ms | 10720 KB |