oj.uz

Submission #970471

# Submission time Handle Problem Language Result Execution time Memory
970471 2024-04-26T15:03:02 Z jadai007 Bob (COCI14_bob) C++14
120 / 120
 532 ms 21992 KB 
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int n,m, arr[1001][1001];
ll dp1[1001][1001], dp2[1001][1001], ans;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i<=n; ++i) for(int j = 1; j<=m; ++j) cin >> arr[i][j];
    for(int i = 1; i<=n; ++i){
        for(int j = 1; j<=m; ++j){
            if(arr[i][j] == arr[i][j - 1]) dp1[i][j] = dp1[i][j - 1] + 1;
            else dp1[i][j] = 1;
        }
    }
    for(int j = 1; j<=m; ++j){
        for(int i = 1; i<=n; ++i){
            if(arr[i][j] == arr[i - 1][j]) dp2[i][j] = dp2[i - 1][j] + 1;
            else dp2[i][j] = 1;
        }
    }
    for(int i = 1; i<=n; ++i){
        for(int j = 1; j<=m; ++j){
            ll M = dp1[i][j], N = dp2[i][j];
            int k = j - 1;
            ans+=N;
            while(k > j - M){
                N = min(N, dp2[i][k]);
                ans+=N;
                k--;
            }
        }
    }
    cout << ans;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 19792 KB Output is correct
2 Correct 484 ms 20044 KB Output is correct
3 Correct 530 ms 21944 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19796 KB Output is correct
2 Correct 229 ms 19920 KB Output is correct
3 Correct 527 ms 21992 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 19924 KB Output is correct
2 Correct 528 ms 21844 KB Output is correct
3 Correct 532 ms 21792 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 19792 KB Output is correct
2 Correct 509 ms 20208 KB Output is correct
3 Correct 529 ms 21984 KB Output is correct