제출 #1162337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162337		Newtonabc	Bob (COCI14_bob)	C++20	120 / 120	84 ms	24136 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(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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){
                //clear stack
                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];
            st.push(tmp);
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum+=ans[i][j];
    cout<<sum;
}

• 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