Submission #319928

#	Time	Username	Problem	Language	Result	Execution time	Memory
319928		monus1042	Strah (COCI18_strah)	C++17	55 / 110	1072 ms	23780 KiB

strah

// 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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11