oj.uz

Submission #228184

# Submission time Handle Problem Language Result Execution time Memory
228184 2020-04-30T06:52:13 Z VEGAnn Strah (COCI18_strah) C++14
55 / 110
 899 ms 12672 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1920 KB Output is correct
2 Correct 19 ms 1920 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2048 KB Output is correct
2 Correct 20 ms 1920 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1792 KB Output is correct
2 Correct 19 ms 1920 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 12660 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 899 ms 6240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 12672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -