結果
問題 | No.866 レベルKの正方形 |
ユーザー |
|
提出日時 | 2020-04-07 14:47:55 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 4,737 ms / 6,000 ms |
コード長 | 3,876 bytes |
コンパイル時間 | 2,458 ms |
コンパイル使用メモリ | 77,772 KB |
実行使用メモリ | 477,016 KB |
最終ジャッジ日時 | 2024-07-07 13:11:59 |
合計ジャッジ時間 | 56,292 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.util.Arrays;import java.util.NoSuchElementException;public class Main{public static void main(String[] args) {new Main().run();}static int num(int i,int j,int len,int[][][] cnt,int H,int W,int target) {int sum=0;int INF=Integer.MAX_VALUE/3;for(int v=0;v<26;++v) {int p=i+len-1;int q=j+len-1;int r=i-1;int t=j-1;int a=(p>H||q>W)?INF:(cnt[v][p][q]-cnt[v][r][q]-cnt[v][p][t]+cnt[v][r][t]);if(a==INF) sum=INF;else if(a>0) ++sum;if(sum==target)break;else if(sum+(26-v-1)<target)break;}return sum;}static void run() {FastScanner sc=new FastScanner();int H=sc.nextInt();int W=sc.nextInt();int K=sc.nextInt();int[][][] cnt=new int[26][H+2][W+2];for(int i=1;i<=H;++i) {char[] map=sc.next().toCharArray();for(int v=0;v<26;++v) {for(int j=1;j<=W;++j) {cnt[v][i][j]=cnt[v][i][j-1]+cnt[v][i-1][j]-cnt[v][i-1][j-1];if((int)(map[j-1]-'a')==v) ++cnt[v][i][j];}}}long ans=0;int[][] lower=new int[2][W+1];int[][] upper=new int[2][W+1];for(int i=1;i<=H;++i) {for(int j=1;j<=W;++j) {upper[i%2][j]=Math.max(Math.max(upper[(i-1)%2][j-1],upper[(i-1)%2][j])-1, 0);upper[i%2][j]=Math.max(upper[i%2][j-1]-1, upper[i%2][j]);lower[i%2][j]=Math.max(Math.max(lower[(i-1)%2][j-1],lower[(i-1)%2][j])-1, 0);lower[i%2][j]=Math.max(lower[i%2][j-1]-1, lower[i%2][j]);while(num(i,j,upper[i%2][j],cnt,H,W,K+1)<=K) {++upper[i%2][j];}while(num(i,j,lower[i%2][j],cnt,H,W,K)<K) {++lower[i%2][j];}ans+=upper[i%2][j]-lower[i%2][j];}}System.out.println(ans);}void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}}class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;}else{ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}public String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while(isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while(true){if ('0' <= b && b <= '9') {n *= 10;n += b - '0';}else if(b == -1 || !isPrintableChar(b)){return minus ? -n : n;}else{throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}public double nextDouble() { return Double.parseDouble(next());}}