oj.uz

Submission #91905

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

int n,m;
int a[maxn][maxn];
int d[maxn][maxn];
int 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;
            int 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 3 ms 888 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 23 ms 4984 KB Output is correct

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 14840 KB Output is correct
2 Correct 68 ms 10224 KB Output is correct
3 Correct 62 ms 10244 KB Output is correct

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17912 KB Output is correct
2 Correct 70 ms 10240 KB Output is correct
3 Incorrect 62 ms 10204 KB Output isn't correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 17912 KB Output is correct
2 Correct 63 ms 10232 KB Output is correct
3 Incorrect 64 ms 10104 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 18080 KB Output is correct
2 Correct 64 ms 10108 KB Output is correct
3 Incorrect 62 ms 10232 KB Output isn't correct