oj.uz

Submission #314842

# Submission time Handle Problem Language Result Execution time Memory
314842 2020-10-21T13:16:24 Z Fischer Strah (COCI18_strah) C++14
110 / 110
 301 ms 8312 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2010;
char mat[maxn][maxn];
int n, m;
int arr[maxn], ta[maxn];
using ll = long long;
ll ans[maxn];

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

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> mat[i];
    }
    ll res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            arr[j + 1] = mat[i][j] != '#' ? arr[j + 1] + 1 : 0;
            ta[j + 1] = arr[j + 1];
        }
        stack<int> s;
        s.push(0); 
        ll sum = 0;
        for (int j = 1; j <= m; ++j) {
            ll delta = 0;
            int temp = j;
            while (!s.empty() && ta[s.top()] > ta[j]) {
                temp = s.top(); s.pop();
                delta += (calc(ta[temp]) - calc(ta[s.top()])) * calc(j - temp);
                sum -= (calc(ta[temp]) - calc(ta[s.top()])) * (j - temp);
            }
            delta -= (calc(ta[j]) - calc(ta[s.top()])) * calc(j - temp);
            sum += (calc(ta[j]) - calc(ta[s.top()])) * (j - temp);
            sum += calc(ta[j]);
            ans[j] = ans[j-1] + sum - delta;
            ta[temp] = ta[j];
            if (ta[j] > ta[s.top()]) {
                s.push(temp);
            }
        }
        for (int j = 1; j <= m; ++j) {
            res += ans[j];
        }
    }
    cout << res << endl;
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1024 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1024 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3064 KB Output is correct
2 Correct 170 ms 5696 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 5528 KB Output is correct
2 Correct 258 ms 7672 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3576 KB Output is correct
2 Correct 185 ms 6004 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4224 KB Output is correct
2 Correct 213 ms 6904 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 8312 KB Output is correct
2 Correct 281 ms 8132 KB Output is correct