제출 #1281062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281062		paronmanukyan	Strah (COCI18_strah)	C++20	110 / 110	113 ms	20276 KiB

strah

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define no_el(x, y) x.find(y) == x.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vct vector
#define vct2dll vct<vct<ll>>
#define vct2dint vct<vct<int>>
#define vct2dchar vct<vct<char>>
#define vct2dbool vct<vct<bool>>
#define vct3dll vct<vct<vct<ll>>>
#define vct3dint vct<vct<vct<int>>>
#define vct3dchar vct<vct<vct<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(nullptr);                                                            \
  cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

int main()
{
	FASTIO
	int n, m; cin >> n >> m;
    vector <string> tv(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> tv[i];
        tv[i] = "X" + tv[i];
    }
    
    vector <vector <int>> dp(n + 1, vector <int>(m + 1));
    for (int i = 1; i <= m; ++i) {
        if (tv[n][i] == '#') 
            dp[n][i] = 0;
        else 
            dp[n][i] = 1;
    }

    for (int i = n - 1; i >= 1; --i) {
        for (int j = 1; j <= m; ++j) {
            if (tv[i][j] == '#') 
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i + 1][j] + 1;
        }
    }

    ll ans = 0;
    for (int ln = 1; ln <= n; ++ln) {
        vector <ll> a(m + 1);
        vector <ll> l(m + 1), r(m + 1);
        for (int i = 1; i <= m; ++i) {
            a[i] = dp[ln][i];
            l[i] = i;
            r[i] = m - i + 1;
        }

        stack <int> st;
        st.push(m);
        
        for (int i = m - 1; i >= 1; --i) {
            while (!st.empty() && a[i] < a[st.top()]) {
                l[st.top()] = st.top() - i;
                st.pop();
            }
            st.push(i);
        }

        while (!st.empty()) st.pop();

        st.push(1);
        for (int i = 2; i <= m; ++i) {
            while (!st.empty() && a[i] <= a[st.top()]) {
                r[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }

        for (int i = 1; i <= m; ++i) {
            //cout << ln << " " << i << " " << a[i] << " " << l[i] << " " << r[i] << "\n";
            ans += (l[i] * (l[i] - 1) / 2) * r[i] * a[i] * (a[i] + 1) / 2;
            ans += (r[i] * (r[i] + 1) / 2) * l[i] * a[i] * (a[i] + 1) / 2;
        }
    }

    cout << ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11