Submission #556352

#	Time	Username	Problem	Language	Result	Execution time	Memory
556352		racsosabe	Bob (COCI14_bob)	C++14	12 / 120	172 ms	11988 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++){
			//cout << i << " -> ";
			while(!pos.empty() and h[pos.back()] >= h[i]){
				int at = pos.back(); pos.pop_back();
				//cout <<  1ll * (h[at] - (pos.empty() ? h[at] : h[pos.back()])) * (i - (pos.empty() ? l - 1 : pos.back())) << " ";
				res += 1ll * (h[at] - (pos.empty() ? h[at] : h[pos.back()])) * (i - (pos.empty() ? l - 1 : pos.back()));
			}
			//cout << 1ll * (h[i] - (pos.empty() ? 0 : h[pos.back()])) * (i - (pos.empty() ? l - 1 : pos.back())) << " ";
			res += 1ll * (h[i] - (pos.empty() ? 0 : h[pos.back()])) * (i - (pos.empty() ? l - 1 : pos.back()));
			pos.emplace_back(i);
			//cout << endl;
		}
		pos.pop_back();
		while(!pos.empty()){
			int at = pos.back(); pos.pop_back();
			//cout << 1ll * (h[at] - (pos.empty() ? 0 : h[pos.back()])) * (r - 1 - (pos.empty() ? l - 1 : pos.back())) << " ";
			res += 1ll * (h[at] - (pos.empty() ? 0 : h[pos.back()])) * (r - 1 - (pos.empty() ? l - 1 : pos.back()));
		}
		//cout << endl;
		pos.clear();
		l = r;
	}
	//cout << res << endl;
	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 'int main()':
bob.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bob.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |    scanf("%d", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 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