oj.uz

Submission #45420

# Submission time Handle Problem Language Result Execution time Memory
45420 2018-04-13T09:05:52 Z choikiwon Maxcomp (info1cup18_maxcomp) C++17
60 / 100
 500 ms 4756 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 3 ms 744 KB Output is correct
10 Correct 3 ms 764 KB Output is correct
11 Correct 3 ms 792 KB Output is correct
12 Correct 3 ms 812 KB Output is correct
13 Correct 3 ms 840 KB Output is correct
14 Correct 3 ms 884 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 668 KB Output is correct
11 Correct 3 ms 668 KB Output is correct
12 Correct 3 ms 744 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 792 KB Output is correct
15 Correct 3 ms 812 KB Output is correct
16 Correct 3 ms 840 KB Output is correct
17 Correct 3 ms 884 KB Output is correct
18 Execution timed out 927 ms 4756 KB Time limit exceeded
19 Halted 0 ms 0 KB -