Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 405
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n,m;
- char a[N][N];
- int h[N];
- int b[N][N];
- int ans[50];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n;
- for(int i=1; i<=n; i++){
- string tmp;
- cin >> tmp;
- m = tmp.size();
- for(int j=1; j<=m; j++){
- a[i][j] = tmp[j-1];
- }
- }
- }
- void calc(int msk){
- vector<int> x(m+1,-1);
- vector<int> y(m+1,-1);
- for(int day=1; day <= n; day++){
- for(int j=1; j<=m; j++){
- if (msk>>(a[day][j]-'A')&1){
- if (day==1) h[j]=1;
- else h[j]++;
- }
- else h[j] = 0;
- }
- stack<int> st;
- for(int i=1; i<=m; i++){
- while (st.size() && h[st.top()]>=h[i]) st.pop();
- if (st.size()) x[i] = st.top()+1;
- else x[i] = 1;
- st.push(i);
- }
- while (st.size()) st.pop();
- for(int i=m; i>=1; i--){
- while (st.size() && h[st.top()]>h[i]) st.pop();
- if (st.size()) y[i] = st.top()-1;
- else y[i] = m;
- st.push(i);
- }
- for(int i=1; i<=m; i++) ans[msk]+=h[i]*(i-x[i]+1)*(y[i]-i+1);
- }
- }
- void proc()
- {
- int mm = 1<<5;
- for(int msk = 1; msk < mm; msk++){
- calc(msk);
- }
- int res=0;
- for(int i=1; i<mm; i++){
- if (__builtin_popcount(i)==3) res += ans[i];
- if (__builtin_popcount(i)==2) res -= 3*ans[i];
- if (__builtin_popcount(i)==1) res += 6*ans[i];
- }
- cout << res;
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement