oj.uz

Submission #517950

# Submission time Handle Problem Language Result Execution time Memory
517950 2022-01-23T08:01:51 Z Be_dos Maxcomp (info1cup18_maxcomp) C++17
60 / 100
 500 ms 36252 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

struct Segtree {
    int32_t** segtree;

    Segtree(int32_t n, int32_t m) {
        segtree = new int32_t*[n];
        for(int32_t i = 0; i < n; i++) {
            segtree[i] = new int32_t[m];
            for(int32_t j = 0; j < m; j++)
                segtree[i][j] = 2'000'000'000;
        }
    }

    int32_t get_min(int32_t right1, int32_t right2) {
        int32_t res = 2'000'000'000;
        for(int32_t i = 0; i < right1; i++)
            for(int32_t j = 0; j < right2; j++)
                res = std::min(res, segtree[i][j]);
        return res;
    }

    void set(int32_t ind1, int32_t ind2, int32_t val) {
        segtree[ind1][ind2] = val;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int32_t n, m;
    std::cin >> n >> m;

    int32_t** arr = new int32_t*[n];
    for(int32_t i = 0; i < n; i++) {
        arr[i] = new int32_t[m];
        for(int32_t j = 0; j < m; j++)
            std::cin >> arr[i][j];
    }

    std::pair<int32_t, int32_t>* order = new std::pair<int32_t, int32_t>[n * m];
    for(int32_t i = 0; i < n; i++)
        for(int32_t j = 0; j < m; j++)
            order[i * m + j] = {i, j};
    std::sort(order, order + n * m, [&](std::pair<int32_t, int32_t> p1, std::pair<int32_t, int32_t> p2) {
        return arr[p1.first][p1.second] < arr[p2.first][p2.second];
    });

    int32_t ans = 0;
    Segtree segtree_lt(n, m), segtree_lb(n, m), segtree_rt(n, m), segtree_rb(n, m);
    for(int32_t i = 0; i < n * m; i++) {
        ans = std::max(ans, arr[order[i].first][order[i].second] - order[i].first - order[i].second - segtree_lt.get_min(order[i].first + 1, order[i].second + 1));
        ans = std::max(ans, arr[order[i].first][order[i].second] + order[i].first - order[i].second - segtree_lb.get_min(n - order[i].first, order[i].second + 1));
        ans = std::max(ans, arr[order[i].first][order[i].second] - order[i].first + order[i].second - segtree_rt.get_min(order[i].first + 1, m - order[i].second));
        ans = std::max(ans, arr[order[i].first][order[i].second] + order[i].first + order[i].second - segtree_rb.get_min(n - order[i].first, m - order[i].second));

        segtree_lt.set(order[i].first, order[i].second, arr[order[i].first][order[i].second] - order[i].first - order[i].second);
        segtree_lb.set(n - order[i].first - 1, order[i].second, arr[order[i].first][order[i].second] + order[i].first - order[i].second);
        segtree_rt.set(order[i].first, m - order[i].second - 1, arr[order[i].first][order[i].second] - order[i].first + order[i].second);
        segtree_rb.set(n - order[i].first - 1, m - order[i].second - 1, arr[order[i].first][order[i].second] + order[i].first + order[i].second);
    }

    std::cout << ans - 1;
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 312 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 11 ms 332 KB Output is correct
10 Correct 9 ms 404 KB Output is correct
11 Correct 11 ms 408 KB Output is correct
12 Correct 9 ms 324 KB Output is correct
13 Correct 9 ms 336 KB Output is correct
14 Correct 9 ms 432 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 312 KB Output is correct
12 Correct 11 ms 332 KB Output is correct
13 Correct 9 ms 404 KB Output is correct
14 Correct 11 ms 408 KB Output is correct
15 Correct 9 ms 324 KB Output is correct
16 Correct 9 ms 336 KB Output is correct
17 Correct 9 ms 432 KB Output is correct
18 Execution timed out 1077 ms 36252 KB Time limit exceeded
19 Halted 0 ms 0 KB -