Guest User

Untitled

a guest
Feb 14th, 2021
1,110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define rep(i,a,n) for (int i=a;i<n;i++)
  6. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  7. #define pb push_back
  8. #define mp make_pair
  9. #define all(x) (x).begin(),(x).end()
  10. #define fi first
  11. #define se second
  12. #define SZ(x) ((int)(x).size())
  13. typedef vector<int> VI;
  14. typedef long long ll;
  15. typedef pair<int,int> PII;
  16. typedef double db;
  17. mt19937 mrand(random_device{}());
  18. const ll mod=998244353;
  19. int rnd(int x) { return mrand() % x;}
  20. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  21. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  22. // head
  23. const int N=2010;
  24. int n,m,nxt[N][N],alive[N];
  25. char s[N][N];
  26. bitset<N> sm[N];
  27. VI ex[N];
  28. ll ans=0;
  29. int main() {
  30.     scanf("%d%d",&n,&m);
  31.     for (int i=0;i<n;i++) scanf("%s",s[i]);
  32.     rep(j,0,m) {
  33.         nxt[n-1][j]=n-1;
  34.         per(i,0,n-1) if (s[i][j]==s[i+1][j]) nxt[i][j]=nxt[i+1][j]; else nxt[i][j]=i;
  35.     }
  36.     rep(i,0,n) rep(k,0,m) sm[i][k]=s[i][k]!=s[i][k-1];
  37.     rep(i,0,n) {
  38.         rep(j,i,n) ex[j].clear();
  39.         rep(j,0,m) ex[nxt[i][j]].pb(j);
  40.         rep(j,0,m) alive[j]=1;
  41.         rep(j,i,n) {
  42.             if (j!=i) {
  43.                 bitset<N> bs=sm[i]|sm[j];
  44.                 int c=alive[0],d=0;
  45.                 for (int k=1;k<m;k++) {
  46.                     if (bs[k]) c=0;
  47.                     if (alive[k]) d+=c,c+=1;
  48.                 }
  49.                 ans+=d;
  50.             }
  51.             for (auto x:ex[j]) alive[x]=0;
  52.  
  53.         }
  54.     }
  55.     printf("%lld\n",ans);
  56. }
Advertisement
Add Comment
Please, Sign In to add comment