Submission #1126122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126122		Art	Strah (COCI18_strah)	C++20	110 / 110	148 ms	468 KiB

strah

// Art - Bui Hai Dang
// Keep typing, keep loving

// #pragma GCC optimize("02,unroll-loops")
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, n)       for (int i = 0, _n = (n); i < _n; ++i)

#define __Art__         int main()

const int N = 2e3 + 10;

using namespace std;

int n, m;
int h[N], L[N], R[N];

// long long f[N];

long long calc() {
    stack<int> stl, str;
    FOR (i, 1, m) {
        while (!stl.empty() && h[i] <= h[stl.top()]) {
            stl.pop();
        }
        L[i] = (stl.empty() ? 0 : stl.top()) + 1;
        stl.push(i);
    }
    REV (i, m, 1) {
        while (!str.empty() && h[i] < h[str.top()]) { // tránh lặp i với (i+1)
            str.pop();
        }
        R[i] = (str.empty() ? m + 1 : str.top()) - 1;
        str.push(i);
    }

    auto sum = [&] (int x) {
        return x * (x + 1) / 2;
    };
    long long res = 0;
    FOR (i, 1, m) if (h[i] != 0) {
        int lenl = i - L[i] + 1, lenr = R[i] - i + 1;
        long long cur = 1LL * lenl * sum(lenr) + 1LL * lenr * sum(lenl) - 1LL * lenl * lenr;
        res += 1LL * cur * sum(h[i]);
    }
    // el;
    return res;
}

__Art__ {

    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);

    if (fopen("art.inp", "r")) {
        freopen("art.inp", "r", stdin);
        freopen("art.out", "w", stdout);
    }

    cin >> n >> m;
    long long res = 0;
    FOR (i, 1, n) {
        FOR (j, 1, m) {
            char type;
            cin >> type;
            if (type == '.') {
                ++h[j];
            }
            else {
                h[j] = 0;
            }
        }
        res += calc();
    }    

    cout << res, el;

    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("art.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
strah.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("art.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