답안 #230673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230673	2020-05-11T03:14:53 Z	box_of_donuts	Palindrome-Free Numbers (BOI13_numbers)	Java 11	77.5 / 100	95 ms	11788 KB

numbers

import java.util.*;
import java.io.*;

public class numbers {
  private static String a, b;
  private static Long[][][][][] dp;
  
  private static long palRange(int i, int lst1, int lst2, int blo, int bhi) {
    if (dp[i][lst1+1][lst2+1][blo][bhi] != null) return dp[i][lst1+1][lst2+1][blo][bhi];
    if (i == a.length()) return dp[i][lst1+1][lst2+1][blo][bhi] = 1L;
    long ret = 0;
    for (int k = -1; k <= 9; k++) {
      if (k == -1 && lst1 == -1 && a.charAt(i) == '#') ret += palRange(i+1, k, lst1, 1, 0);
      else if (k == -1) continue;
      if (k == 0 && a.charAt(i) == '#' || k == lst1 || k == lst2) continue;
      if (blo == 1 && k < (a.charAt(i) - '0') || bhi == 1 && k > (b.charAt(i) - '0')) continue;
      ret += palRange(i+1, k, lst1, blo == 1 && k == (a.charAt(i) - '0') ? 1 : 0, 
                      bhi == 1 && k == (b.charAt(i) - '0') ? 1 : 0);
    }
    return dp[i][lst1+1][lst2+1][blo][bhi] = ret;
  }
  
  public static void main(String[] args) throws IOException { 
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    StringTokenizer ST = new StringTokenizer(in.readLine()); 
    a = ST.nextToken(); 
    b = ST.nextToken(); 
    
    while (a.length() < b.length()) a = "#" + a;
    dp = new Long[a.length()+1][11][11][2][2];
    long ans = palRange(0, -1, -1, 1, 1);
    System.out.println(ans);
  
    in.close();
    out.close(); 
  }
}

Subtask #1

17.5 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	10352 KB	Output is correct
2	Incorrect	77 ms	10372 KB	Output isn't correct
3	Correct	82 ms	10616 KB	Output is correct
4	Incorrect	82 ms	10572 KB	Output isn't correct
5	Correct	85 ms	10488 KB	Output is correct
6	Correct	81 ms	10596 KB	Output is correct
7	Correct	76 ms	10224 KB	Output is correct
8	Incorrect	78 ms	10232 KB	Output isn't correct
9	Correct	76 ms	10416 KB	Output is correct
10	Correct	77 ms	10620 KB	Output is correct
11	Correct	78 ms	10252 KB	Output is correct
12	Correct	76 ms	10492 KB	Output is correct
13	Correct	81 ms	10436 KB	Output is correct
14	Incorrect	79 ms	10856 KB	Output isn't correct
15	Incorrect	83 ms	10776 KB	Output isn't correct
16	Correct	82 ms	10484 KB	Output is correct
17	Correct	80 ms	11000 KB	Output is correct
18	Correct	79 ms	10360 KB	Output is correct
19	Correct	85 ms	10868 KB	Output is correct
20	Incorrect	89 ms	10716 KB	Output isn't correct

Subtask #2

60.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	10896 KB	Output is correct
2	Correct	82 ms	11004 KB	Output is correct
3	Correct	89 ms	11000 KB	Output is correct
4	Correct	94 ms	10848 KB	Output is correct
5	Incorrect	81 ms	10992 KB	Output isn't correct
6	Correct	83 ms	10876 KB	Output is correct
7	Incorrect	80 ms	11056 KB	Output isn't correct
8	Incorrect	81 ms	10588 KB	Output isn't correct
9	Incorrect	86 ms	10976 KB	Output isn't correct
10	Incorrect	85 ms	11100 KB	Output isn't correct
11	Correct	84 ms	10868 KB	Output is correct
12	Incorrect	85 ms	10792 KB	Output isn't correct
13	Incorrect	84 ms	10740 KB	Output isn't correct
14	Incorrect	79 ms	10740 KB	Output isn't correct
15	Incorrect	82 ms	10928 KB	Output isn't correct
16	Correct	86 ms	10900 KB	Output is correct
17	Correct	77 ms	10616 KB	Output is correct
18	Correct	83 ms	10648 KB	Output is correct
19	Correct	78 ms	10732 KB	Output is correct
20	Correct	86 ms	10512 KB	Output is correct
21	Correct	91 ms	11000 KB	Output is correct
22	Correct	80 ms	10616 KB	Output is correct
23	Correct	90 ms	11032 KB	Output is correct
24	Correct	78 ms	10744 KB	Output is correct
25	Correct	88 ms	10872 KB	Output is correct
26	Correct	91 ms	11016 KB	Output is correct
27	Correct	85 ms	11020 KB	Output is correct
28	Correct	95 ms	10888 KB	Output is correct
29	Correct	82 ms	10616 KB	Output is correct
30	Correct	76 ms	10480 KB	Output is correct
31	Correct	89 ms	11460 KB	Output is correct
32	Correct	78 ms	10616 KB	Output is correct
33	Correct	88 ms	11600 KB	Output is correct
34	Correct	77 ms	10488 KB	Output is correct
35	Correct	82 ms	10872 KB	Output is correct
36	Correct	85 ms	10996 KB	Output is correct
37	Correct	85 ms	10800 KB	Output is correct
38	Correct	88 ms	10900 KB	Output is correct
39	Correct	88 ms	11788 KB	Output is correct
40	Correct	80 ms	10492 KB	Output is correct
41	Correct	86 ms	10868 KB	Output is correct
42	Correct	79 ms	10572 KB	Output is correct
43	Correct	85 ms	10996 KB	Output is correct
44	Correct	84 ms	10872 KB	Output is correct
45	Correct	85 ms	11128 KB	Output is correct