oj.uz

Submission #82239

# Submission time Handle Problem Language Result Execution time Memory
82239 2018-10-29T15:26:01 Z ngot23 Bob (COCI14_bob) C++11
120 / 120
 192 ms 24512 KB 
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=1005;
int f[N][N], m, n, a[N][N], luu[N], dem, s[N], top;
long long ans, b[N];

void tinh() {
    rep(i, 1, dem) b[i]=0;
    top=0;
    rep(i, 1, dem) {
        while(top&&luu[i]<=luu[s[top]]) --top;
        b[i]=1ll*(i-s[top])*luu[i]+b[s[top]];
        ans+=b[i];
        s[++top]=i;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> m >> n;
    rep(i, 1, m)
        rep(j, 1, n) {
            cin >> a[i][j];
            f[i][j]=1;
            if(a[i-1][j]==a[i][j]) f[i][j]+=f[i-1][j];
        }

    rep(i, 1, m) {
        int ptr=1;
        a[i][n+1]=-1;
        while(ptr<=n) {
            int j=ptr;
            dem=0;
            for( ; j<=n ; ++j) {
                luu[++dem]=f[i][j];
                if(a[i][j]!=a[i][j+1]) {
                    tinh();
                    break;
                }
            }
            ptr=j+1;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 8760 KB Output is correct
2 Correct 83 ms 10768 KB Output is correct
3 Correct 79 ms 12776 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 12784 KB Output is correct
2 Correct 80 ms 14844 KB Output is correct
3 Correct 78 ms 16928 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 16928 KB Output is correct
2 Correct 79 ms 18640 KB Output is correct
3 Correct 75 ms 20720 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 20740 KB Output is correct
2 Correct 89 ms 22608 KB Output is correct
3 Correct 88 ms 24512 KB Output is correct