Advertisement
MinhNGUYEN2k4

Untitled

Sep 18th, 2021
702
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 405
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n,m;
  28. char a[N][N];
  29. int h[N];
  30. int b[N][N];
  31. int ans[50];
  32.  
  33. void readfile()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0);cout.tie(0);
  37.     if (fopen(Task".inp","r"))
  38.     {
  39.         freopen(Task".inp","r",stdin);
  40.         //freopen(Task".out","w",stdout);
  41.     }
  42.     cin >> n;
  43.     for(int i=1; i<=n; i++){
  44.         string tmp;
  45.         cin >> tmp;
  46.         m = tmp.size();
  47.         for(int j=1; j<=m; j++){
  48.             a[i][j] = tmp[j-1];
  49.         }
  50.     }
  51. }
  52.  
  53. void calc(int msk){
  54.     vector<int> x(m+1,-1);
  55.     vector<int> y(m+1,-1);
  56.     for(int day=1; day <= n; day++){
  57.         for(int j=1; j<=m; j++){
  58.             if (msk>>(a[day][j]-'A')&1){
  59.                 if (day==1) h[j]=1;
  60.                 else h[j]++;
  61.             }
  62.             else h[j] = 0;
  63.         }
  64.         stack<int> st;
  65.         for(int i=1; i<=m; i++){
  66.             while (st.size() && h[st.top()]>=h[i]) st.pop();
  67.             if (st.size()) x[i] = st.top()+1;
  68.             else x[i] = 1;
  69.             st.push(i);
  70.         }
  71.         while (st.size()) st.pop();
  72.         for(int i=m; i>=1; i--){
  73.             while (st.size() && h[st.top()]>h[i]) st.pop();
  74.             if (st.size()) y[i] = st.top()-1;
  75.             else y[i] = m;
  76.             st.push(i);
  77.         }
  78.         for(int i=1; i<=m; i++) ans[msk]+=h[i]*(i-x[i]+1)*(y[i]-i+1);
  79.     }
  80. }
  81.  
  82. void proc()
  83. {
  84.     int mm = 1<<5;
  85.     for(int msk = 1; msk < mm; msk++){
  86.         calc(msk);
  87.     }
  88.     int res=0;
  89.     for(int i=1; i<mm; i++){
  90.         if (__builtin_popcount(i)==3) res += ans[i];
  91.         if (__builtin_popcount(i)==2) res -= 3*ans[i];
  92.         if (__builtin_popcount(i)==1) res += 6*ans[i];
  93.     }
  94.     cout << res;
  95. }
  96.  
  97. signed main()
  98. {
  99.     readfile();
  100.     proc();
  101.     return 0;
  102. }
  103.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement