Submission #337127

#	Time	Username	Problem	Language	Result	Execution time	Memory
337127		BeanZ	Strah (COCI18_strah)	C++14	110 / 110	230 ms	8248 KiB

strah

// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e3 + 5;
long long mod = 1e9 + 7;
const int lim = 2e5;
const int lg = 18;
const int base = 311;
const long double eps = 1e-6;
char a[N][N];
ll cnt[N], l[N], r[N];
ll sum(ll u){
    return u * (u + 1) / 2;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
            if (a[i][j] == '.') cnt[j]++;
            else cnt[j] = 0;
        }
        vector<ll> st;
        for (int j = 1; j <= m; j++){
            while (st.size()){
                if (cnt[st.back()] >= cnt[j]) st.pop_back();
                else break;
            }
            if (st.size()) l[j] = st.back() + 1;
            else l[j] = 1;
            st.push_back(j);
        }
        st.clear();
        for (int j = m; j >= 1; j--){
            while (st.size()){
                if (cnt[st.back()] > cnt[j]) st.pop_back();
                else break;
            }
            if (st.size()) r[j] = st.back() - 1;
            else r[j] = m;
            st.push_back(j);
        }
        for (int j = 1; j <= m; j++){
            ll lf = j - l[j] + 1;
            ll rt = r[j] - j + 1;
            ll tot = lf * sum(rt) + rt * sum(lf) - lf * rt;
            ans = ans + tot * sum(cnt[j]);
        }
    }
    cout << ans;
}
/*
3 3
...
...
...
Ans:

Out:
*/

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   21 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
strah.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   22 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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