Submission #91908

#	Time	Username	Problem	Language	Result	Execution time	Memory
91908		vex	Bob (COCI14_bob)	C++14	120 / 120	131 ms	12580 KiB

bob

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12