Submission #556352

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
556352	2022-05-03T03:13:36 Z	racsosabe	Bob (COCI14_bob)	C++14	12 / 120	172 ms	11988 KB

#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

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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	468 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	2832 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	23 ms	3180 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	25 ms	3388 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	27 ms	3336 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	113 ms	7480 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	144 ms	7236 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	143 ms	11988 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	172 ms	7124 KB	Output isn't correct
2	Halted	0 ms	0 KB	-