Submission #1171570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171570		javkhlantogs	Bob (COCI14_bob)	C++20	120 / 120	239 ms	16216 KiB

bob

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ll n,m,i,j,k,q,sum=0,cnt,ans=0;
	cin>>n>>m;
	vector<vector<ll>> a(n,vector<ll>(m)),b(n,vector<ll>(m));
	for(i=0 ; i<n ; i++){
		for(j=0 ; j<m ; j++){
			cin>>a[i][j];
			if(i>0 and a[i][j]==a[i-1][j]) b[i][j]=b[i-1][j]+1;
				else b[i][j]=1;
		}
	}
	for(i=0 ; i<n ; i++){
		sum=0;
		stack<pair<ll,ll>> st;
		for(j=0 ; j<m ; j++){
			if(j!=0 and a[i][j]!=a[i][j-1]){
				while(st.size()>=1) st.pop();
				sum=0;
			}
			if(st.size()==0){
				st.push({b[i][j],1});
				sum+=b[i][j];
			}
				else{
					cnt=1;
					while(st.size()>0 and st.top().first>=b[i][j]){
						sum-=st.top().first*st.top().second;
						cnt+=st.top().second;
						st.pop();	
					}
					st.push({b[i][j],cnt});
					sum+=b[i][j]*cnt;
				}
			ans+=sum;
		}
	}
	cout<<ans<<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