oj.uz

답안 #197440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197440 2020-01-21T07:45:03 Z GSmerch Maxcomp (info1cup18_maxcomp) C++14
60 / 100
 500 ms 57268 KB 
#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;


using namespace std;

#define fi first
#define se second
#define sz(x) (x).size()
#define pll pair<ll,ll >
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define endln '\n'
#define cont continue

const ll MaxN = 1e3 + 100;
const ll LogN = 20;
ll Inf = 1e18;
const ll dx[4] = { 0,1,0,-1 };
const ll dy[4] = { 1,0,-1,0 };

bool used[MaxN][MaxN];
ll Mt[MaxN][MaxN];

struct el{
    ll x, y, a;
};
int main() {

#ifdef LOCAL
    ifstream cin("input.txt");
    ofstream cout("output.txt");
#else
    //ifstream cin("points.in");
    //ofstream cout("points.out");
#endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    ll N, M;
    cin>>N>>M;
    ll Mx = 0;
    set<ll > St;
    for(int i = 1;i<=N;i++){
        for(int j =1;j<=M;j++){
            cin>>Mt[i][j];
            used[i][j] = 1;
           St.insert(Mt[i][j]);
        }
    }
    queue<el > BFS;
    ll Ans = -Inf;
    for(ll x : St){
         for(int i = 1;i<=N;i++){
            for(int j =1;j<=M;j++){
                used[i][j] = 1;
                if(x == Mt[i][j]){
                    BFS.push({i,j,1});
                }
            }
        }
        while(sz(BFS)){
            el a = BFS.front();
            BFS.pop();
            Ans = max(Ans, x - Mt[a.x][a.y] - a.a);
            if(!used[a.x][a.y]) cont;
            used[a.x][a.y] = 0;
            for(int i =0;i<4;i++){
                if(used[a.x + dx[i]][a.y + dy[i]]){
                    BFS.push({a.x + dx[i], a.y + dy[i], a.a+1});
                }
            }
        }
    }
    cout<<Ans;





    return 0;
}

Compilation message

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:44:8: warning: unused variable 'Mx' [-Wunused-variable]
     ll Mx = 0;
        ^~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 376 KB Output is correct
2 Correct 25 ms 376 KB Output is correct
3 Correct 24 ms 352 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 253 ms 892 KB Output is correct
10 Correct 175 ms 784 KB Output is correct
11 Correct 173 ms 888 KB Output is correct
12 Correct 175 ms 888 KB Output is correct
13 Correct 173 ms 760 KB Output is correct
14 Correct 244 ms 844 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 25 ms 376 KB Output is correct
10 Correct 25 ms 376 KB Output is correct
11 Correct 24 ms 352 KB Output is correct
12 Correct 253 ms 892 KB Output is correct
13 Correct 175 ms 784 KB Output is correct
14 Correct 173 ms 888 KB Output is correct
15 Correct 175 ms 888 KB Output is correct
16 Correct 173 ms 760 KB Output is correct
17 Correct 244 ms 844 KB Output is correct
18 Execution timed out 1084 ms 57268 KB Time limit exceeded
19 Halted 0 ms 0 KB -