Submission #230673

#	Time	Username	Problem	Language	Result	Execution time	Memory
230673		box_of_donuts	Palindrome-Free Numbers (BOI13_numbers)	Java	77.50 / 100	95 ms	11788 KiB

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
• Subtask 2: 60 / 75