제출 #1343093

#제출 시각아이디문제언어결과실행 시간메모리
1343093thnhannStrah (COCI18_strah)C++20
110 / 110
99 ms4784 KiB
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=5e5;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    int total_sum = 0;
    vector<int> h(m, 0);
    vector<int> L(m), R(m);
    vector<int> st;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '.') h[j]++;
            else h[j] = 0;
        }

        st.clear();
        for (int j = 0; j < m; ++j) {
            while (!st.empty() && h[st.back()] >= h[j]) {
                st.pop_back();
            }
            L[j] = st.empty() ? -1 : st.back();
            st.push_back(j);
        }

        st.clear();
        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && h[st.back()] > h[j]) {
                st.pop_back();
            }
            R[j] = st.empty() ? m : st.back();
            st.push_back(j);
        }

        for (int j = 0; j < m; ++j) {
            if (h[j] == 0) continue;
            
            int x = j - L[j];
            int y = R[j] - j;
            
            int c = (h[j] * (h[j] + 1)) / 2;
            int ways = (x * y * (x + y)) / 2;
            
            total_sum += c * ways;
        }
    }

    cout << total_sum; el;
    return 0;
}
// "Can i get a kiss? And can u make it last forever?"
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...