oj.uz

Submission #412915

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

const int mxN = 1e3+5;
int a[mxN][mxN];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
bool vis[mxN][mxN];

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

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;
    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);
        q.pop();
        vis[u_node][v_node] = true;
        for(int k = 0; k < 4; k++) {
            int x = u_node+dx[k], y = v_node+dy[k];
            if(check(x, y, n, m))
                q.push({{x, y}, value+1});
        }
    }
    return mx-mn-subset_size;
}

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:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
maxcomp.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |             scanf("%d", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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