oj.uz

Submission #319928

# Submission time Handle Problem Language Result Execution time Memory
319928 2020-11-06T20:09:41 Z monus1042 Strah (COCI18_strah) C++17
55 / 110
 1000 ms 23780 KB 
// NK
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)

//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ord_set;

void solve(){
	int n,m; cin>>n>>m;
	char ma[n+1][m+1];
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			cin>>ma[i][j];
		}
	}

	ll ans = 0;
	int acc[n+1][m+1];
	memset(acc, false, sizeof acc);
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			acc[i][j] = acc[i][j-1] + acc[i-1][j] - acc[i-1][j-1];
			if (ma[i][j] == '.') acc[i][j]++;
		}
	}

	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			for (int k=i; k<=n; k++){
				int lo = j, hi = m+1;
				while(lo+1 != hi){
					int mid = (lo + hi) / 2;
					if (acc[k][mid] - acc[k][j-1] - acc[i-1][mid] + acc[i-1][j-1] == (k-i+1) * (mid-j+1)){
						lo = mid;
					}else hi = mid;
				}
				ll aux = (ll)(lo - j + 1) * (ll)(lo - j + 2) / 2 * (ll)(k - i + 1);
				if (acc[k][lo] - acc[k][j-1] - acc[i-1][lo] + acc[i-1][j-1] == (k-i+1) * (lo-j+1)) ans = ans + aux;
			}
		}
	}
	cout<<ans<<'\n';
}

int main(){
	Bolivia_is_nice;
	int t = 1; //cin>>t;
	while(t--)
	solve();
	
	return 0;
}
/*
  ~/.emacs
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 916 KB Output is correct
2 Correct 317 ms 996 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 876 KB Output is correct
2 Correct 311 ms 876 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 916 KB Output is correct
2 Correct 335 ms 1004 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 6508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 14820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 9444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 1900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 23780 KB Time limit exceeded
2 Halted 0 ms 0 KB -