# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
543201 | ahmet34 | Bob (COCI14_bob) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
const int INF = 2e9, N = 55, M = 998244353, LOG = 16;
const ll LINF = 1e18;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
vector v(n, vector<int>(m));
for(auto& vi : v) for(int& x: vi) cin >> x;
vector dp(n, vector<ll>(m));
auto isValid = [&] (int x, int y) {
return x >= 0 && y >= 0 && x < n && y < m;
};
ll ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
dp[i][j] = 1;
bool adj = false;
if(isValid(i-1, j) and v[i-1][j] == v[i][j]) {
dp[i][j] += dp[i-1][j];
adj = true;
}
if(isValid(i, j-1) and v[i][j] == v[i][j-1]) {
dp[i][j] += dp[i][j-1];
adj = true;
}
if(isValid(i-1, j-1) and adj and v[i-1][j-1] == v[i][j])
dp[i][j] -= dp[i-1][j-1];
ans += dp[i][j];
//cout << dp[i][j] << ' ';
}
//cout << endl;
}
cout << ans;
}