Submission #5547325


Source Code Expand

Copy
import java.util.*;

public class Main {
	static int mod = 1000000007;
  static int size = 200000;
	static long[] fac = new long[size];
	static long[] finv = new long[size];
	static long[] inv = new long[size];
  static int INF = Integer.MAX_VALUE;

 	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		String[] s = new String[n];
		for(int i = 0; i < n; i++){
			s[i] = scanner.next();
		}
		char[][] c = new char[n][m];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				c[i][j] = s[i].charAt(j);
			}
		}
		int[][] right = new int[n][m];
		for(int i = 0; i < n; i++){
			int count = 0;
			for(int j = 0; j < m; j++){
				if(c[i][j] == '.'){
					right[i][j] = count;
					count++;
				}else{
					count = 0;
				}
			}
		}
		int[][] left = new int[n][m];
		for(int i = 0; i < n; i++){
			int count = 0;
			for(int j = m-1; j >= 0; j--){
				if(c[i][j] == '.'){
					left[i][j] = count;
					count++;
				}else{
					count = 0;
				}
			}
		}
		int[][] up = new int[n][m];
		for(int i = m-1; i >= 0; i--){
			int count = 0;
			for(int j = 0; j < n; j++){
				if(c[j][i] == '.'){
					up[j][i] = count;
					count++;
				}else{
					count = 0;
				}
			}
		}
		int[][] down = new int[n][m];
		for(int i = m-1; i >= 0; i--){
			int count = 0;
			for(int j = n-1; j >= 0; j--){
				if(c[j][i] == '.'){
					down[j][i] = count;
					count++;
				}else{
					count = 0;
				}
			}
		}
		int[][] sum = new int[n][m];
		long ans = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				sum[i][j] += (up[i][j] + down[i][j]) * (left[i][j] + right[i][j]);
				ans += sum[i][j];
			}
		}
		System.out.println(ans);
	}
  static class Pair implements Comparable<Pair>{
    int x, y;
    Pair(int a, int b){
        x = a;
        y = b;
    }
    @Override
    public boolean equals(Object o){
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair p = (Pair) o;
        return x == p.x && y == p.y;
    }
    @Override
    public int compareTo(Pair p){
        return x == p.x ? y - p.y : x - p.x; //xで昇順にソート
        //return (x == p.x ? y - p.y : x - p.x) * -1; //xで降順にソート
        //return y == p.y ? x - p.x : y - p.y;//yで昇順にソート
        //return (y == p.y ? x - p.x : y - p.y)*-1;//yで降順にソート
    }
  }
  //繰り返し二乗法
  public static long pow(long x, long n){
    long ans = 1;
    while(n > 0){
      if((n & 1) == 1){
        ans = ans * x;
        ans %= mod;
      }
      x = x * x % mod;
      n >>= 1;
    }
    return ans;
  }

  //fac, inv, finvテーブルの初期化、これ使う場合はinitComb()で初期化必要
	public static  void initComb(){
		fac[0] = finv[0] = inv[0] = fac[1] = finv[1] = inv[1] = 1;
		for (int i = 2; i < size; ++i) {
			fac[i] = fac[i - 1] * i % mod;
			inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod;
			finv[i] = finv[i - 1] * inv[i] % mod;
		}
	}

	//nCk % mod
	public static long comb(int n, int k){
		return fac[n] * finv[k] % mod * finv[n - k] % mod;
	}

	//n! % mod
	public static long fact(int n){
		return fac[n];
	}

	//(n!)^-1 with % mod
	public static long finv(int n){
		return finv[n];
	}

  static class UnionFind {
    int[] parent;
    public UnionFind(int size) {
      parent = new int[size];
      Arrays.fill(parent, -1);
    }
    public boolean unite(int x, int y) {
      x = root(x);
      y = root(y);
      if (x != y) {
        if (parent[y] < parent[x]) {
          int tmp = y;
          y = x;
          x = tmp;
        }
        parent[x] += parent[y];
        parent[y] = x;
        return true;
      }
      return false;
    }
    public boolean same(int x, int y) {
      return root(x) == root(y);
    }
    public int root(int x) {
      return parent[x] < 0 ? x : (parent[x] = root(parent[x]));
    }
    public int size(int x) {
      return -parent[root(x)];
    }
  }
	public static int upperBound(long[] array, long value) {
			 int low = 0;
			 int high = array.length;
			 int mid;
			 while( low < high ) {
					 mid = ((high - low) >>> 1) + low; // (high + low) / 2
					 if( array[mid] <= value ) {
							 low = mid + 1;
					 } else {
							 high = mid;
					 }
			 }
			 return low;
	 }
	 public static final int lowerBound(final long[] arr, final long value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        if (arr[mid] < value) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}
  //n,mの最大公約数
  public static int gcd(int n, int m){
    if(m > n) return gcd(m,n);
    if(m == 0) return n;
    return gcd(m, n%m);
  }
}

Submission Info

Submission Time
Task C - 右折
User rmkt
Language Java8 (OpenJDK 1.8.0)
Score 400
Code Size 5054 Byte
Status
Exec Time 786 ms
Memory 152772 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 543 ms 148656 KB
02.txt 535 ms 147952 KB
03.txt 559 ms 150472 KB
04.txt 560 ms 152772 KB
05.txt 529 ms 147616 KB
06.txt 503 ms 152324 KB
07.txt 532 ms 149496 KB
08.txt 533 ms 146836 KB
09.txt 521 ms 150256 KB
10.txt 519 ms 147688 KB
11.txt 537 ms 149756 KB
12.txt 531 ms 148696 KB
13.txt 461 ms 150952 KB
14.txt 468 ms 146684 KB
15.txt 532 ms 148060 KB
16.txt 496 ms 148332 KB
17.txt 459 ms 148612 KB
18.txt 468 ms 149096 KB
19.txt 477 ms 149824 KB
20.txt 498 ms 150744 KB
21.txt 533 ms 147528 KB
22.txt 528 ms 148692 KB
23.txt 537 ms 147004 KB
24.txt 539 ms 146904 KB
25.txt 541 ms 146408 KB
26.txt 518 ms 148504 KB
27.txt 511 ms 146428 KB
28.txt 516 ms 146056 KB
29.txt 786 ms 23252 KB
30.txt 95 ms 25556 KB
31.txt 95 ms 24788 KB
32.txt 93 ms 28116 KB
33.txt 94 ms 24660 KB
34.txt 93 ms 23252 KB
35.txt 94 ms 23252 KB
36.txt 94 ms 23508 KB
s1.txt 94 ms 25940 KB
s2.txt 93 ms 24020 KB
s3.txt 94 ms 23764 KB