Submission #101133

#	Time	Username	Problem	Language	Result	Execution time	Memory
101133		Ort	Strah (COCI18_strah)	C++11	110 / 110	132 ms	4344 KiB

strah

#include<iostream>
#include<stack>
#include<vector>
#define ll long long
 
using namespace std;
 
int n, m;
vector<int> a;
ll sol = 0;

void f() {
  	stack<int> s;
  	vector<int> l(m,0), r(m,0);
  	ll x = 0;
 	for (int i=0;i<m;i++) {
   		while (!s.empty() && a[i] <= a[s.top()]) {
    		r[s.top()] = i; s.pop();
    	}
    	l[i] = s.empty() ? -1 : s.top();
    	s.push(i);
  	}
  	while(!s.empty()){
    	r[s.top()] = m;
    	s.pop();
  	}
  	for(int i=0;i<m;i++) {
  		ll b = i - l[i] - 1, c = r[i] - i - 1, e = a[i];
  		x += (b+1)*(c+1)*(e*(e+1)/2)+(e*(e+1)/2)*(c*(c+1)/2)*(b+1)+(c+1)*(e*(e+1)/2)*(b*(b+1)/2);
  	}
  	sol += x;
}
 
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	cin >> n >> m;
  	a.resize(m,0);
  	for(int i=0;i<n;i++) {
    	for(int j=0;j<m;j++) {
      		char c; cin >> c;
      		if (c == '.') a[j]++;
      		else a[j] = 0;
    	}
    	f();
  	}
  	cout << sol;
  return 0;
}

• 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