oj.uz

Submission #90956

# Submission time Handle Problem Language Result Execution time Memory
90956 2018-12-25T09:59:24 Z Bruteforceman Strah (COCI18_strah) C++11
110 / 110
 157 ms 45348 KB 
#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

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.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2760 KB Output is correct
2 Correct 6 ms 3012 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3012 KB Output is correct
2 Correct 6 ms 3204 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3300 KB Output is correct
2 Correct 6 ms 3452 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10568 KB Output is correct
2 Correct 79 ms 19520 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 20124 KB Output is correct
2 Correct 133 ms 29676 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 29676 KB Output is correct
2 Correct 87 ms 30524 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30524 KB Output is correct
2 Correct 123 ms 36324 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 41420 KB Output is correct
2 Correct 150 ms 45348 KB Output is correct