Submission #45420

#	Time	Username	Problem	Language	Result	Execution time	Memory
45420		choikiwon	Maxcomp (info1cup18_maxcomp)	C++17	60 / 100	927 ms	4756 KiB

maxcomp

#include<bits/stdc++.h>
using namespace std;

int N, M;
int A[1010][1010];

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * M, 2e9);
    }
    void upd(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = min(tree[n], val);
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 2e9;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return min(L, R);
    }
} bit1, bit2;

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            scanf("%d", &A[i][j]);
        }
    }

    int ans = -2e9;

    bit1.init();
    bit2.init();
    for(int i = N - 1; i >= 0; i--) {
        for(int j = 0; j < M; j++) {
            bit1.upd(j, A[i][j] + i - j, 0, M - 1, 1);
            bit2.upd(j, A[i][j] + i + j, 0, M - 1, 1);
        }
        for(int j = 0; j < M; j++) {
            ans = max(ans, A[i][j] + i - j - bit1.quer(0, j - 1, 0, M - 1, 1) - 1);
            ans = max(ans, A[i][j] + i + j - bit2.quer(j + 1, M - 1, 0, M - 1, 1) - 1);
        }
    }

    bit1.init();
    bit2.init();
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            bit1.upd(j, A[i][j] - (i - j), 0, M - 1, 1);
            bit2.upd(j, A[i][j] - (i + j), 0, M - 1, 1);
        }
        for(int j = 0; j < M; j++) {
            ans = max(ans, A[i][j] - (i - j) - bit1.quer(j + 1, M - 1, 0, M - 1, 1) - 1);
            ans = max(ans, A[i][j] - (i + j) - bit2.quer(0, j - 1, 0, M - 1, 1) - 1);
        }
    }

    printf("%d", ans);
}

Compilation message (stderr)

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
maxcomp.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40