Submission #1162331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162331		Newtonabc	Bob (COCI14_bob)	C++20	0 / 120	262 ms	24052 KiB

bob

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int arr[N][N],ex[N][N],ans[N][N];
int n,m;
void print(int a[N][N]){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<a[i][j] <<" ";
        }
        cout<<"\n";
    }
    cout<<"\n";
}
signed main(){
    cin>>n >>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>arr[i][j];
    for(int i=1;i<=n;i++) for(int j=m;j>=1;j--){
        if(arr[i][j]!=arr[i][j+1]){
            ex[i][j]=1;
            continue;
        }
        ex[i][j]=ex[i][j+1]+1;
    }
    for(int j=1;j<=m;j++){
        stack<pair<int,int>> st;
        for(int i=1;i<=n;i++){
            pair<int,int> tmp={i,1};
            if(arr[i][j]!=arr[i-1][j] || i==1){
                while(!st.empty()) st.pop();
                st.push(tmp);
                ans[i][j]=ex[i][j];
                continue;
            }
            //make monotonic stack
            while(!st.empty() && ex[i][j]<=ex[st.top().first][j]){
                tmp.second+=st.top().second;
                st.pop();
            }
            ans[i][j]=tmp.second*ex[i][j];
            if(!st.empty()) ans[i][j]+=ans[st.top().first][j];
        }
    }
    long long sum=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum+=ans[i][j];
    cout<<sum;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12