Submission #412927

#	Time	Username	Problem	Language	Result	Execution time	Memory
412927		aris12345678	Maxcomp (info1cup18_maxcomp)	C++14	15 / 100	12 ms	204 KiB

maxcomp

#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 (stderr)

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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40