oj.uz

Submission #91906

# Submission time Handle Problem Language Result Execution time Memory
91906 2018-12-31T11:19:37 Z vex Bob (COCI14_bob) C++14
84 / 120
 135 ms 12716 KB 
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;

int n,m;
int a[maxn][maxn];
long long d[maxn][maxn];
long long br[maxn];

long long sol=0LL;
stack<int>ms;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)cin>>a[i][j];

    for(int i=0;i<m;i++)d[n-1][i]=1;
    for(int i=n-2;i>=0;i--)
        for(int j=0;j<m;j++)
        {
            d[i][j]=1;
            if(a[i][j]==a[i+1][j])d[i][j]+=d[i+1][j];
        }

    /*cout<<endl;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)cout<<d[i][j]<<" ";
        cout<<endl;
    }*/

    //cout<<endl;
    for(int i=0;i<n;i++)
    {
        while(!ms.empty())ms.pop();
        ms.push(0);
        br[0]=d[i][0];
        sol+=br[0];

        for(int j=1;j<n;j++)
        {
            while(!ms.empty()&& d[i][ms.top()]>=d[i][j] && a[i][ms.top()]==a[i][j])
            {
                ms.pop();
            }

            br[j]=0LL;
            long long num;
            if(ms.empty())num=j+1;
            else
            {
                num=j-ms.top();
                if(a[i][ms.top()]==a[i][j])br[j]=br[ms.top()];
            }

            ms.push(j);
            br[j]+=num*d[i][j];
            sol+=br[j];
        }

        //for(int j=0;j<m;j++)cout<<br[j]<<" ";
        //cout<<endl;
    }

    //cout<<endl;
    cout<<sol<<endl;
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12700 KB Output is correct
2 Correct 66 ms 12536 KB Output is correct
3 Correct 64 ms 12536 KB Output is correct

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12536 KB Output is correct
2 Correct 74 ms 12536 KB Output is correct
3 Incorrect 65 ms 12500 KB Output isn't correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 12544 KB Output is correct
2 Correct 68 ms 12716 KB Output is correct
3 Incorrect 67 ms 12568 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 12684 KB Output is correct
2 Correct 133 ms 12712 KB Output is correct
3 Incorrect 67 ms 12664 KB Output isn't correct