oj.uz

Submission #98961

# Submission time Handle Problem Language Result Execution time Memory
98961 2019-02-27T19:03:27 Z SecretAgent007 Strah (COCI18_strah) C++17
110 / 110
 176 ms 23928 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 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 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2560 KB Output is correct
2 Correct 8 ms 2560 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2604 KB Output is correct
2 Correct 7 ms 2560 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9600 KB Output is correct
2 Correct 83 ms 17584 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 15848 KB Output is correct
2 Correct 146 ms 23132 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10268 KB Output is correct
2 Correct 95 ms 18688 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12544 KB Output is correct
2 Correct 120 ms 21660 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 23928 KB Output is correct
2 Correct 176 ms 23892 KB Output is correct