Submission #1226779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226779		dibamboo23	Bob (COCI14_bob)	C++20	120 / 120	64 ms	8264 KiB

bob

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define sz size()

using namespace std;

[[maybe_unused]]const int e6=1e6;
[[maybe_unused]]const int e7=1e7;
[[maybe_unused]]const int e8=1e8;
[[maybe_unused]]const int e9=1e9;

inline int rd(){
	int num;cin>>num;
	return num;
}

inline ll rdll(){
	ll num;cin>>num;
	return num;
}

[[maybe_unused]]const ll inf=1e18+7;
[[maybe_unused]]const ll MOD=1e9+7;
[[maybe_unused]]const int N=1e3+3;

int a[N][N];
vector<pair<int,int>>g[N];
int p[N][N];
int val[N];

void code(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	ll res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]!=a[i][j-1])p[i][j]=1;
			else p[i][j]=p[i][j-1]+1;
			if(a[i][j]!=a[i-1][j])g[j].clear();
			if(g[j].empty())g[j].push_back({p[i][j],1}),val[j]=p[i][j];
			else{
				int cnt=1;
				while(!g[j].empty()&&g[j].back().F>=p[i][j]){
					val[j]-=g[j].back().F*g[j].back().S;
					cnt+=g[j].back().S;
					g[j].pop_back();
				}
				val[j]+=p[i][j]*cnt;
				g[j].push_back({p[i][j],cnt});
			}
			res+=val[j];
		}
	}
	cout<<res;
}




signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int tt=1;
	// cin>>tt;
	while(tt--)code(),cout<<"\n";
}

• 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