Submission #81641

#	Time	Username	Problem	Language	Result	Execution time	Memory
81641		IvanC	Strah (COCI18_strah)	C++17	110 / 110	121 ms	752 KiB

strah

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;

const int MAXN = 2010;

char entrada[MAXN];
int tamanho[MAXN],esq[MAXN],dir[MAXN],N,M;
ii vetor[MAXN];
ll tot_area;

ll somatorio(ll x){
	return (x*(x+1))/2;
}

ll soma_especial(ll x){
	return somatorio(x) - x;
}

ll calculate_area(){

	//printf("##########\n");
	ll resp = 0;
	stack<int> pilha;
	vetor[0] = ii(-1,0);
	pilha.push(0);

	for(int i = 1;i<=M;i++){
		vetor[i] = ii(tamanho[i],i);
		while(!pilha.empty() && vetor[pilha.top()] > vetor[i]){
			dir[pilha.top()] = i;
			pilha.pop();
		}
		esq[i] = pilha.top();
		pilha.push(i);
	}

	while(!pilha.empty()){
		dir[pilha.top()] = M+1;
		pilha.pop();
	}

	for(int i = 1;i<=M;i++){
		esq[i]++;
		dir[i]--;
		//printf("I %d %d %d %lld\n",i,(i - esq[i] + 1),(dir[i] - i + 1),somatorio(tamanho[i]));
		int a = i - esq[i] + 1;
		int b = dir[i] - i + 1;
		resp += 1LL*(b*somatorio(a) + a*soma_especial(b))*somatorio(tamanho[i]);
	}
	//printf("#########\n");

	return resp;

}

int main(){

	scanf("%d %d",&N,&M);

	for(int linha = 0;linha<N;linha++){
		scanf("%s",entrada);
		for(int i = 0;i<M;i++){
			if(entrada[i] == '.'){
				tamanho[i+1]++;
			}
			else{
				tamanho[i+1] = 0;
			}
		}
		//for(int i = 1;i<=M;i++) printf("%d ",tamanho[i]);
		//printf("\n");
		tot_area += calculate_area();
	}

	printf("%lld\n",tot_area);

	return 0;
}

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:61: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:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",entrada);
   ~~~~~^~~~~~~~~~~~~~

• 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