제출 #1162330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162330		Newtonabc	Bob (COCI14_bob)	C++20	0 / 120	246 ms	12324 KiB

bob

#include<bits/stdc++.h>
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";
}
int 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