oj.uz

Submission #1057622

# Submission time Handle Problem Language Result Execution time Memory
1057622 2024-08-14T01:44:23 Z vjudge1 Bob (COCI14_bob) C++17
120 / 120
 79 ms 18004 KB 
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

const int MAXN = 1005;

int n, m;
int a[MAXN][MAXN];
int s[MAXN][MAXN];

typedef long long llint;

struct RectangleInfo {
    int count;
    int value;
    int height;
    llint areaSum;
    RectangleInfo(int _count = 0, int _value = 0, int _height = 0, llint _areaSum = 0)
        : count(_count), value(_value), height(_height), areaSum(_areaSum) {}
};

llint ans = 0;

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

    cin >> n >> m;

    // Input grid values
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];

    // Process each row
    for (int i = 0; i < n; ++i) {
        stack<RectangleInfo> S;
        S.push(RectangleInfo(0, -1, 0, 0));  // Initial dummy entry

        for (int j = 0; j < m; ++j) {
            s[i][j] = 1;

            // If current cell matches the one above, increase the height
            if (i > 0 && a[i-1][j] == a[i][j])
                s[i][j] += s[i-1][j];

            int combinedCount = 1;
            // Combine rectangles with the same value and greater height
            while (S.top().value == a[i][j] && S.top().height >= s[i][j]) {
                combinedCount += S.top().count;
                S.pop();
            }

            llint currentAreaSum = combinedCount * static_cast<llint>(s[i][j]);
            if (S.top().value == a[i][j])
                currentAreaSum += S.top().areaSum;

            ans += currentAreaSum;
            S.push(RectangleInfo(combinedCount, a[i][j], s[i][j], currentAreaSum));
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7388 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7744 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7772 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7772 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 14912 KB Output is correct
2 Correct 39 ms 10060 KB Output is correct
3 Correct 39 ms 10052 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 18004 KB Output is correct
2 Correct 38 ms 10312 KB Output is correct
3 Correct 45 ms 10076 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 18004 KB Output is correct
2 Correct 40 ms 10248 KB Output is correct
3 Correct 37 ms 10072 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 18004 KB Output is correct
2 Correct 41 ms 10064 KB Output is correct
3 Correct 37 ms 10152 KB Output is correct