Submission #90956

#	Time	Username	Problem	Language	Result	Execution time	Memory
90956		Bruteforceman	Strah (COCI18_strah)	C++11	110 / 110	157 ms	45348 KiB

strah

#include "bits/stdc++.h"
using namespace std;
int P[2002][2002];
int n, m;
char s[2004][2004];
const int inf = 1e8;

int summation(int p, int q) {
	if(p > q) return 0;
	int ans = 0;
	ans += (q * (q + 1)) / 2;
	ans -= (p * (p - 1)) / 2;
	return ans; 
}

long long solve(int col) {
	stack <int> sk;
	long long sum = 0;
	long long tot = 0;
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		while(!sk.empty() && P[sk.top()][col] >= P[i][col]) {
			int cur = sk.top(); 
			sk.pop();
			int prev = (sk.empty()) ? 0 : sk.top();
			sum -= 1LL * summation(1, P[cur][col]) * (cur - prev);
			tot -= 1LL * summation(1, P[cur][col]) * summation(prev + 1, cur);
		} 
		int cur = i;
		int prev = (sk.empty()) ? 0 : sk.top();
		sk.push(cur);
		sum += 1LL * summation(1, P[cur][col]) * (cur - prev);
		tot += 1LL * summation(1, P[cur][col]) * summation(prev + 1, cur);
		ans += 1LL * (i + 1) * sum - tot;
	}
	return ans;
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%s", s[i] + 1);
	}
	for(int j = 0; j <= m; j++) {
		P[0][j] = inf;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			P[i][j] = (s[i][j] == '.') ? P[i][j - 1] + 1 : 0;
		}
	}
	long long ans = 0;
	for(int i = 1; i <= m; i++) {
		ans += solve(i);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

strah.cpp: In function 'int main(int, const char**)':
strah.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
strah.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s[i] + 1);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11