Submission #556696

#	Time	Username	Problem	Language	Result	Execution time	Memory
556696		racsosabe	Bob (COCI14_bob)	C++14	24 / 120	131 ms	13924 KiB

bob

#include<bits/stdc++.h>
using namespace::std;
 
const int N = 1000 + 5;
 
int n;
int m;
int h[N];
int a[N][N];
 
void build_level(int row){
	for(int i = 1; i <= m; i++){
		if(a[row - 1][i] == a[row][i]) h[i] += 1;
		else h[i] = 1;
	}
}
 
long long solve_row(int row){
	int l = 1, r = 1;
	vector<int> pos;
	long long res = 0;
	while(l <= m){
		while(r <= m and a[row][l] == a[row][r]) r++;
		for(int i = l; i < r; i++){
			while(!pos.empty() and h[pos.back()] >= h[i]){
				int at = pos.back(); pos.pop_back();
				int len = i - 1 - (pos.size() <= 1 ? l - 1 : pos[pos.size() - 2]);
				int h_pr = pos.empty() ? 0 : h[pos.back()];
				int h_pr2 = pos.size() <= 1 ? 0 : h[pos.size() - 2];
				res += 1ll * len * (h_pr - h_pr2);
			}
			res += 1ll * (h[i] - (pos.empty() ? 0 : h[pos.back()])) * (i - (pos.empty() ? l - 1 : pos.back()));
			pos.emplace_back(i);
		}
		while(!pos.empty()){
			int at = pos.back(); pos.pop_back();
			int len = r - 1 - (pos.size() <= 1 ? l - 1 : pos[pos.size() - 2]);
			int h_pr = pos.empty() ? 0 : h[pos.back()];
			int h_pr2 = pos.size() <= 1 ? 0 : h[pos.size() - 2];
			res += 1ll * len * (h_pr - h_pr2);
		}
		l = r;
	}
	return res;
}
 
long long solve(){
	long long ans = 0;
	for(int i = 1; i <= n; i++){
		build_level(i);
		ans += solve_row(i);
	}
	return ans;
}
 
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%d", &a[i][j]);
		}
	}
	printf("%lld\n", solve());
	return 0;
}

Compilation message (stderr)

bob.cpp: In function 'long long int solve_row(int)':
bob.cpp:26:9: warning: unused variable 'at' [-Wunused-variable]
   26 |     int at = pos.back(); pos.pop_back();
      |         ^~
bob.cpp:36:8: warning: unused variable 'at' [-Wunused-variable]
   36 |    int at = pos.back(); pos.pop_back();
      |        ^~
bob.cpp: In function 'int main()':
bob.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bob.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |    scanf("%d", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12