oj.uz

Submission #319920

# Submission time Handle Problem Language Result Execution time Memory
319920 2020-11-06T19:51:54 Z monus1042 Strah (COCI18_strah) C++17
22 / 110
 1000 ms 23924 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 unsigned 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(){
	// change ULL
	int n,m; cin>>n>>m;
	char ma[n][m];
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			cin>>ma[i][j];
		}
	}

	ll ans = 0;
	int acc[n+1][m+1];
	memset(acc, false, sizeof acc);
	for (int i=0; i<n; i++){
		for (int j=0; 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=0; i<n; i++){
		for (int j=0; j<m; j++){
			for (int k=i; k<n; k++){
				for (int l=j; l<m; ++l){
					int area = (k-i+1) * (l-j+1), ac = acc[k][l] - acc[k][j-1] - acc[i-1][l] + acc[i-1][j-1];
					if (area == ac){
						ans += (ll)area;
					}
				}
			}
		}
	}
	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 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 6648 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 1049 ms 14948 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 1045 ms 9448 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 1051 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 1025 ms 23924 KB Time limit exceeded
2 Halted 0 ms 0 KB -