oj.uz

Submission #412927

# Submission time Handle Problem Language Result Execution time Memory
412927 2021-05-27T19:33:12 Z aris12345678 Maxcomp (info1cup18_maxcomp) C++14
15 / 100
 12 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e3+5;
int a[mxN][mxN];
int dx[2] = {1, 0}, dy[2] = {0, 1};

bool check(int i, int j, int n, int m) {
    return i >= 0 && j >= 0 && i < n && j < m;
}

int bfs(int i, int j, int n, int m) {
    queue<pair<pair<int, int>, int> > q;
    q.push({{i, j}, 1});
    int mx = a[i][j], mn = a[i][j], subset_size = 1, ans = 0;
    while(!q.empty()) {
        int u_node = q.front().first.first, v_node = q.front().first.second;
        int value = q.front().second;
        if(mx < a[u_node][v_node]) {
            mx = a[u_node][v_node];
            subset_size = value;
        }
        if(mx == a[u_node][v_node])
            subset_size = min(subset_size, value);
        if(mn > a[u_node][v_node]) {
            mn = a[u_node][v_node];
            subset_size = value;
        }
        if(mn == a[u_node][v_node])
            subset_size = min(subset_size, value);
        ans = max(ans, mx-mn-subset_size);
        // cout << mx << " " << mn << " " << subset_size << " " << ans << "\n";
        q.pop();
        for(int k = 0; k < 2; k++) {
            int x = u_node+dx[k], y = v_node+dy[k];
            if(check(x, y, n, m)) {
                q.push({{x, y}, value+1});
                // cout << x << " " << y << "\n";
            }
        }
    }
    // cout << i << " " << j << " " << ans << "\n";
    return ans;
}

int main() {
    int n, m;
    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 = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            ans = max(ans, bfs(i, j, n, m));
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
maxcomp.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |             scanf("%d", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 204 KB Output is correct
2 Correct 10 ms 204 KB Output is correct
3 Correct 12 ms 204 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -