結果
| 問題 | No.866 レベルKの正方形 |
| ユーザー |
 Grenache
|
| 提出日時 | 2019-08-20 14:16:00 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 5,015 ms / 6,000 ms |
| コード長 | 6,910 bytes |
| コンパイル時間 | 4,003 ms |
| コンパイル使用メモリ | 80,816 KB |
| 実行使用メモリ | 459,628 KB |
| 最終ジャッジ日時 | 2024-10-06 12:11:07 |
| 合計ジャッジ時間 | 69,765 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder866_2 {private static Scanner sc;private static Printer pr;static long stime = 0;private static void stTime() {stime = System.currentTimeMillis();}private static void prTime() {pr.printf("time : %d%n", System.currentTimeMillis() - stime);}private static void solve() {int h = sc.nextInt();int w = sc.nextInt();int k = sc.nextInt();// stTime();char[][] c = new char[h][];for (int i = 0; i < h; i++) {c[i] = sc.nextCharArray(w);// c[i] = sc.next().toCharArray();}// prTime();int[][][] dp = new int[26][h][w];final int INF = Integer.MAX_VALUE / 2;for (char cc = 'a'; cc <= 'z'; cc++) {int cci = cc - 'a';// for (int i = 0; i < h; i++) {// Arrays.fill(dp[cci][i], INF);// }for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (c[i][j] == cc) {dp[cci][i][j] = 1;} else {dp[cci][i][j] = INF;}}}for (int i = h - 1; i >= 0; i--) {for (int j = w - 1; j >= 0; j--) {int max = Math.min(h - i, w - j);int tmp = dp[cci][i][j];if (i + 1 < h && j + 1 < w) {tmp = Math.min(tmp, dp[cci][i + 1][j + 1] + 1);}if (i + 1 < h) {tmp = Math.min(tmp, dp[cci][i + 1][j] + 1);}if (j + 1 < w) {tmp = Math.min(tmp, dp[cci][i][j + 1] + 1);}if (tmp > max) {tmp = INF;}dp[cci][i][j] = tmp;}}}// prTime();long ans = 0;int[] tmp = new int[27];for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {int max = Math.min(h - i, w - j);tmp[26] = max + 1;;for (int l = 0; l < 26; l++) {if (dp[l][i][j] == INF) {tmp[l] = max + 1;} else {tmp[l] = dp[l][i][j];}}Arrays.sort(tmp);ans += tmp[k] - tmp[k - 1];}}pr.println(ans);// prTime();}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}static class Scanner {BufferedReader br;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}private boolean isPrintable(int ch) {return ch >= '!' && ch <= '~';}private boolean isCRLF(int ch) {return ch == '\n' || ch == '\r' || ch == -1;}private int nextPrintable() {try {int ch;while (!isPrintable(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}return ch;} catch (IOException e) {throw new NoSuchElementException();}}String next() {try {int ch = nextPrintable();StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (isPrintable(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int nextInt() {try {// parseInt from Integer.parseInt()boolean negative = false;int res = 0;int limit = -Integer.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Integer.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}int multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}long nextLong() {try {// parseLong from Long.parseLong()boolean negative = false;long res = 0;long limit = -Long.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Long.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}long multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}float nextFloat() {return Float.parseFloat(next());}double nextDouble() {return Double.parseDouble(next());}String nextLine() {try {int ch;while (isCRLF(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (!isCRLF(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}char[] nextCharArray(int n) {char[] ret = new char[n];try {int ch = nextPrintable();int i = 0;do {ret[i++] = (char)ch;} while (isPrintable(ch = br.read()));return ret;} catch (IOException e) {throw new NoSuchElementException();}}int[] nextIntArray(int n) {int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = sc.nextInt();}return ret;}int[][] nextIntArrays(int n, int m) {int[][] ret = new int[m][n];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret[j][i] = sc.nextInt();}}return ret;}void close() {try {br.close();} catch (IOException e) {// throw new NoSuchElementException();}}}static class Printer extends PrintWriter {Printer(OutputStream out) {super(out);}void printInts(int... a) {StringBuilder sb = new StringBuilder(32);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}void printLongs(long... a) {StringBuilder sb = new StringBuilder(64);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}void printStrings(String... a) {StringBuilder sb = new StringBuilder(32);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}}}