oj.uz

Submission #1100212

# Submission time Handle Problem Language Result Execution time Memory
1100212 2024-10-13T09:55:29 Z vjudge1 Maxcomp (info1cup18_maxcomp) C++17
60 / 100
 164 ms 300420 KB 
//UNSTOPPABLE
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define tpii pair <pair <int,int> , int>
#define bruh cout << "NO\n"
using namespace std;
using namespace __gnu_pbds;
const int N = 107 , M = 5001;
int mod = 1e9 + 7;
const int INF = 1e9;
int n,m,a[N][N],num[N][N],val[M],used[M],mx[M][M],mn[M][M];
vector <int> g[M];
int dist[M][M];
void Goldik(){
	cin >> n >> m;
	int cur = 0;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin >> a[i][j];
			num[i][j] = ++cur;
			val[cur] = a[i][j];
		}
	}
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			int x = num[i][j];
			if(i != 1){
				g[x].pb(num[i - 1][j]);
			}
			if(j != 1){
				g[x].pb(num[i][j - 1]);
			}
			if(i != n){
				g[x].pb(num[i + 1][j]);
			}
			if(j != m){
				g[x].pb(num[i][j + 1]);
			}
		}
	}
	for(int i = 1 ; i <= cur ; i++){
		for(int j = 1 ; j <= cur ; j++){
			dist[i][j] = INF;
			mx[i][j] = -INF;
			mn[i][j] = INF;
		}
	}
	int ans = -INF;
	for(int i = 1 ; i <= cur ; i++){
		for(int j = 1 ; j <= cur ; j++) used[j] = 0;
		deque <int> q = {};
		q.pb(i);
		dist[i][i] = 1;
		used[i] = 1;
		mx[i][i] = val[i];
		mn[i][i] = val[i];
		while(q.size()){
			int v = q.front();
			q.ppf();
			used[v] = 1;
			for(auto to : g[v]){
				if(!used[to]){
					if(dist[i][to] == INF || dist[i][to] > dist[i][v] + 1){
						dist[i][to] = dist[i][v] + 1;
						mx[i][to] = max(mx[i][v] , val[to]);
						mn[i][to] = min(mn[i][v] , val[to]);
						q.pb(to);
					}
				}
			}
		}
		for(int j = 1 ; j <= cur ; j++){
			ans = max(ans , mx[i][j] - mn[i][j] - dist[i][j]);
		}
	}
	cout << ans;
}
//5e7 -> max
//rewai mnogo zadach vozmozhno odna iz nih gde to popadetsya
//returning winter prime?
//chem prowe tem luchshe
signed main(/*AZ AZDAN UZDIKSIZ*/){
	//freopen("txt.in","r",stdin);
	//freopen("txt.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	srand(time(0));
	int TT = 1;
	// cin >> TT;
	for(int i = 1 ; i <= TT ; i++){
		//cout << "Case " << i << ": ";
		Goldik();
	}
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121680 KB Output is correct
2 Correct 22 ms 121428 KB Output is correct
3 Correct 25 ms 121428 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8528 KB Output is correct
2 Correct 1 ms 8528 KB Output is correct
3 Correct 1 ms 8528 KB Output is correct
4 Correct 1 ms 8528 KB Output is correct
5 Correct 1 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 1 ms 8528 KB Output is correct
8 Correct 1 ms 8528 KB Output is correct
9 Correct 164 ms 300420 KB Output is correct
10 Correct 140 ms 300340 KB Output is correct
11 Correct 142 ms 300412 KB Output is correct
12 Correct 155 ms 300300 KB Output is correct
13 Correct 159 ms 300364 KB Output is correct
14 Correct 154 ms 300192 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8528 KB Output is correct
2 Correct 1 ms 8528 KB Output is correct
3 Correct 1 ms 8528 KB Output is correct
4 Correct 1 ms 8528 KB Output is correct
5 Correct 1 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 1 ms 8528 KB Output is correct
8 Correct 1 ms 8528 KB Output is correct
9 Correct 21 ms 121680 KB Output is correct
10 Correct 22 ms 121428 KB Output is correct
11 Correct 25 ms 121428 KB Output is correct
12 Correct 164 ms 300420 KB Output is correct
13 Correct 140 ms 300340 KB Output is correct
14 Correct 142 ms 300412 KB Output is correct
15 Correct 155 ms 300300 KB Output is correct
16 Correct 159 ms 300364 KB Output is correct
17 Correct 154 ms 300192 KB Output is correct
18 Runtime error 32 ms 5204 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -