結果
| 問題 | No.866 レベルKの正方形 |
| ユーザー |
 Grenache
|
| 提出日時 | 2019-08-16 23:48:45 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,983 bytes |
| コンパイル時間 | 3,919 ms |
| コンパイル使用メモリ | 80,108 KB |
| 実行使用メモリ | 469,376 KB |
| 最終ジャッジ日時 | 2024-09-23 01:32:24 |
| 合計ジャッジ時間 | 28,717 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 22 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder866_1 {private static Scanner sc;private static Printer pr;private static void solve() {int h = sc.nextInt();int w = sc.nextInt();int k = sc.nextInt();char[][] c = new char[h][];for (int i = 0; i < h; i++) {c[i] = sc.next().toCharArray();}int[][][] cnt = new int[26][h + 1][w + 1];for (char cc = 'a'; cc <= 'z'; cc++) {int cci = cc - 'a';for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (c[i][j] == cc) {cnt[cci][i + 1][j + 1]++;}}}for (int i = 0; i <= h; i++) {for (int j = 0; j <= w; j++) {if (i > 0) {cnt[cci][i][j] += cnt[cci][i - 1][j];}if (j > 0) {cnt[cci][i][j] += cnt[cci][i][j - 1];}if (i > 0 && j > 0) {cnt[cci][i][j] -= cnt[cci][i - 1][j - 1];}}}}int ans = 0;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {int ik = 0, ik1 = 0;{int l = 0;int r = Math.min(h - i, w - j) + 1;while (r - l > 1) {int mid = l + (r - l) / 2;if (f(mid, cnt, i, j) >= k) {// if (data[mid] >= value) {r = mid;} else {l = mid;}}// return r;ik = r;}{int l = 0;int r = Math.min(h - i, w - j) + 1;while (r - l > 1) {int mid = l + (r - l) / 2;if (f(mid, cnt, i, j) >= k + 1) {// if (data[mid] >= value) {r = mid;} else {l = mid;}}// return r;ik1 = r;}int tmp = ik1 - ik;ans += tmp;}}pr.println(ans);}private static Map<Integer, Integer> hm;private static int pi = -1;private static int pj = -1;private static int f(int mid, int[][][] cnt, int i, int j) {if (pi != i || pj != j) {hm.clear();pi = i;pj = j;}Integer tmp1 = hm.get(mid);if (tmp1 != null) {return tmp1;}int tmp = 0;for (int cci = 0; cci < 26; cci++) {int tmp2 = cnt[cci][i + mid - 1 + 1][j + mid - 1 + 1]- cnt[cci][i + mid - 1 + 1][j - 1 + 1]- cnt[cci][i - 1 + 1][j + mid - 1 + 1]+ cnt[cci][i - 1 + 1][j - 1 + 1];if (tmp2 > 0) {tmp++;}}hm.put(mid, tmp1);return tmp;}// ---------------------------------------------------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();}}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);}}}