oj.uz

Submission #81641

# Submission time Handle Problem Language Result Execution time Memory
81641 2018-10-25T17:41:30 Z IvanC Strah (COCI18_strah) C++17
110 / 110
 121 ms 752 KB 
#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

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

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 576 KB Output is correct
2 Correct 4 ms 576 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 576 KB Output is correct
2 Correct 5 ms 580 KB Output is correct

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 752 KB Output is correct
2 Correct 71 ms 752 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 752 KB Output is correct
2 Correct 102 ms 752 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 752 KB Output is correct
2 Correct 71 ms 752 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 752 KB Output is correct
2 Correct 72 ms 752 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 752 KB Output is correct
2 Correct 121 ms 752 KB Output is correct