#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a + n
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b)/gcd(a, b)
#define int long long int
#define ull unsigned long long
#define printarray(arr, n) for(int i= 0;i<n;i++) cout<<arr[i]<<' '; cout<<endl;
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define initdp(a) memset(a, -1, sizeof(a));
#define endl '\n'
#define float long double
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e5 + 5;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin>>n>>m;
int a[n][m];
for(int i= 0;i<n;i++){
for(int j= 0;j<m;j++){
cin>>a[i][j];
}
}
int prefh[n][m], prefv[n][m];
clr(prefh);
clr(prefv);
for(int i= 0;i<n;i++){
for(int j= 0;j<m;j++){
if(j==0) {
prefh[i][j]= 1;
continue;
}
if(a[i][j] == a[i][j-1]){
prefh[i][j] = prefh[i][j-1]+1;
} else {
prefh[i][j] = 1;
}
}
}
for(int j= 0;j<m;j++){
for(int i= 0;i<n;i++){
if(i==0) {
prefv[i][j]= 1;
continue;
}
if(a[i][j] == a[i-1][j]){
prefv[i][j] = prefv[i-1][j]+1;
} else {
prefv[i][j] = 1;
}
}
}
int dp1[n][m];
bool flag[n][m];
clr(flag);
// dp1[i][j] = max width ending at (i, j)
int dp2[n][m];
// dp2[i][j] = max height ending at (i, j)
for(int i= 0;i<n;i++){
for(int j= 0;j<m;j++){
if(i == 0 && j == 0){
dp1[i][j] = 1;
dp2[i][j] = 1;
continue;
}
if(i == 0){
dp1[i][j] = prefh[i][j];
dp2[i][j] = 1;
}
if(j == 0){
dp2[i][j] = prefv[i][j];
dp1[i][j] = 1;
}
if(i > 0 && j > 0){
if(a[i-1][j-1] == a[i][j]){
dp1[i][j] = min(dp1[i-1][j-1]+1, prefh[i][j]);
} else {
dp1[i][j] = prefh[i][j];
flag[i][j]= true;
}
if(a[i-1][j-1] == a[i][j]){
dp2[i][j] = min(dp2[i-1][j-1]+1, prefv[i][j]);
} else {
dp2[i][j] = prefv[i][j];
flag[i][j]= true;
}
}
}
}
int ans = 0;
for(int i= 0;i<n;i++){
for(int j= 0;j<m;j++){
if(flag[i][j]){
ans += dp1[i][j] + dp2[i][j]-1;
} else {
ans += dp1[i][j] * dp2[i][j];
}
}
}
cout<<ans<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
26 ms |
10368 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
10348 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
10348 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
10348 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
141 ms |
40428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
165 ms |
40428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
167 ms |
40492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
157 ms |
40428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
