fork download 
  1. #pragma GCC optimize ("-Ofast")
  2. #pragma GCC optimize ("-unroll-loops")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. using ll=long long;
  8.  
  9. #define rng(i,a,b) for(int i=int(a);i<int(b);i++)
  10. #define rep(i,b) rng(i,0,b)
  11. #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
  12. #define per(i,b) gnr(i,0,b)
  13. #define pb push_back
  14.  
  15. const int nmax=2010;
  16. using B=bitset<nmax>;
  17. char buf[nmax][nmax];
  18. int dif[nmax][nmax];
  19. bool ok[nmax];
  20. B sm[nmax];
  21. vector<int> qs[nmax];
  22.  
  23. int main(){
  24. 	int n,m;
  25. 	scanf("%d%d",&n,&m);
  26. 	rep(i,n)scanf("%s",buf[i]);
  27.  
  28. 	rep(j,m)dif[n-1][j]=n;
  29. 	per(i,n-1)rep(j,m)if(buf[i][j]==buf[i+1][j])dif[i][j]=dif[i+1][j];
  30. 	else dif[i][j]=i+1;
  31.  
  32. 	rep(i,n)rep(j,m-1)if(buf[i][j]!=buf[i][j+1])
  33. 		sm[i].flip(j);
  34.  
  35. 	ll ans=0;
  36. 	rep(i1,n){
  37. 		rep(j,m)ok[j]=1;
  38. 		rep(j,m)if(dif[i1][j]<n)qs[dif[i1][j]].pb(j);
  39. 		rng(i2,i1+1,n){
  40. 			B adj=sm[i1]|sm[i2];
  41. 			for(auto j:qs[i2])ok[j]=false;
  42. 			qs[i2].clear();
  43. 			int cur=0,tot=0;
  44. 			rep(j,m){
  45. 				if(ok[j]){tot+=cur;cur+=1;}
  46. 				if(adj[j])cur=0;
  47. 			}
  48. 			ans+=tot;
  49. 		}
  50. 	}
  51.  
  52. 	printf("%lld\n",ans);
  53. }
  54.  
Success #stdin #stdout 0s 4752KB
comments (?)
stdin 
12 12
abbabaaaaabb
ababaaaaaabb
aaabbbbbabbb
aabababaaaba
abbbaaabaaba
baaababbbaba
aaaaababbaaa
bbabbbbbabaa
bbbabbaabaaa
aabbbaaaabba
babaabababaa
bababaabaaba
stdout 
25
https://ideone.com/jSXhYw
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!