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 <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;
int n, m, grid[1001][1001] = {}, nl[1001][1001] = {};
long long dp[1001][1001];
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> grid[i][j];
nl[i][j] = 1;
if (grid[i][j] == grid[i][j-1]){
nl[i][j] += nl[i][j-1];
}
}
}
for (int i = 1; i <= n; i++){
dp[i][1] = 1;
if (grid[i-1][1] == grid[i][1]){
dp[i][1] += dp[i-1][1];
}
}
for (int c = 2; c <= m; c++){
for (int r = 1; r <= n; r++){
dp[r][c] = nl[r][c];
if (grid[r][c] == grid[r-1][c]){
dp[r][c] += dp[r-1][c];
if (nl[r][c] < nl[r-1][c]){
dp[r][c] -= dp[r-1][c-nl[r][c]];
}
}
}
}
long long ans = 0;
for (int i = 0; i <= n; i++){
for (int j = 0; j <= m; j++){
ans += dp[i][j];
}
}
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |