oj.uz

Submission #91908

# Submission time Handle Problem Language Result Execution time Memory
91908 2018-12-31T11:39:09 Z vex Bob (COCI14_bob) C++14
120 / 120
 131 ms 12580 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<m;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 2 ms 804 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 12580 KB Output is correct
2 Correct 70 ms 12536 KB Output is correct
3 Correct 66 ms 12408 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 12400 KB Output is correct
2 Correct 71 ms 12536 KB Output is correct
3 Correct 66 ms 12508 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 12284 KB Output is correct
2 Correct 67 ms 12240 KB Output is correct
3 Correct 66 ms 12152 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 12152 KB Output is correct
2 Correct 70 ms 12152 KB Output is correct
3 Correct 67 ms 12128 KB Output is correct