Submission #228184

#	Time	Username	Problem	Language	Result	Execution time	Memory
228184		VEGAnn	Strah (COCI18_strah)	C++14	55 / 110	899 ms	12672 KiB

strah

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
char c[N][N];
int pf[N][N], n, m;
ll ans = 0;

int sum(int x1, int y1, int x2, int y2){
    return pf[x2][y2] - pf[x1 - 1][y2] - pf[x2][y1 - 1] + pf[x1 - 1][y1 - 1];
}

ll arith(ll x){
    return x * (x + 1ll) / 2ll;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++){
        cin >> c[i][j];

        pf[i][j] = pf[i - 1][j] + pf[i][j - 1] - pf[i - 1][j - 1] + bool(c[i][j] == '#');
    }

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++){
        if (c[i][j] == '#') continue;

        int len = 1;

        while (i + len <= n && c[i + len][j] != '#')
            len++;

        int ptr = j;

        for (int up = len; up > 0; up--){
            while (ptr + 1 <= m && sum(i, j, i + up - 1, ptr + 1) == 0)
                ptr++;

            ans += arith(ptr - j + 1) * ll(up);
        }
    }

    cout << ans;

    return 0;
}

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