oj.uz

Submission #336742

# Submission time Handle Problem Language Result Execution time Memory
336742 2020-12-16T16:34:32 Z monus1042 Maja (COCI18_maja) C++17
22 / 110
 2 ms 492 KB 
// NK
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)

//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ord_set;

int ma[100][100];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int a,b,n,m;

void solve(){
	cin>>n>>m;
	cin>>a>>b;
	a--, b--;
	int k; cin>>k;
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			cin>>ma[i][j];
		}
	}
	ll dp2[100][100];
	memset(dp2, false, sizeof dp2);
	ll acc = 0;
	for (int j=b; j<m; j++){
		acc += ma[a][j];
		dp2[a][j]=acc;
	}
	acc = 0;
	for (int j=b; j>=0; j--){
		acc += ma[a][j];
		dp2[a][j]=acc;
	}
	acc = 0;
	for (int i=a; i<n; i++){
		acc += ma[i][b];
		dp2[i][b]=acc;
	}
	acc = 0;
	for (int i=a; i>=0; i--){
		acc += ma[i][b];
		dp2[i][b]=acc;
	}
	// now for the quadrants:
	for (int i=a-1; i>=0; i--){
		for (int j=b+1; j<m; j++){
			dp2[i][j] = max(dp2[i+1][j], dp2[i][j-1]) + ma[i][j];
		}
	}
	for (int i=a-1; i>=0; i--){
		for (int j=b-1; j>=0; j--){
			dp2[i][j] = max(dp2[i+1][j], dp2[i][j+1]) + ma[i][j];
		}
	}
	for (int i=a+1; i<n; i++){
		for (int j=b-1; j>=0; j--){
			dp2[i][j] = max(dp2[i-1][j], dp2[i][j+1]) + ma[i][j];
		}
	}
	for (int i=a+1; i<n; i++){
		for (int j=b+1; j<m; j++){
			dp2[i][j] = max(dp2[i-1][j], dp2[i][j-1]) + ma[i][j];
		}
	}
	////
	ll answer = 0;
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			if (i==a && j==b) continue;
			int stepsrem = abs(a-i)+abs(b-j);
			stepsrem*=2;
			stepsrem = k - stepsrem;
			//cout << stepsrem << endl;
			if (stepsrem < 0) continue;
			for (int dir=0; dir<4; ++dir){
				int row = i + dy[dir];
				int col = j + dx[dir];
				if (0<=row && row<n && 0<=col && col<m){
					ll best = ma[i][j] + ma[row][col];
					stepsrem/=2;
					best = best * stepsrem;
					best = best + dp2[i][j] * 2LL - ma[i][j];
					//cout << best << ' ';
					answer = max(answer, best);
				}
			}
			//cout << endl;
		}
	}
	cout << answer << '\n';
}

int main(){
	/*Bolivia_is_nice;
	int t = 1; cin>>t;
	while(t--)
	solve();*/

	Bolivia_is_nice;
	solve();
	
	return 0;
}
/*
  ~/.emacs
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 ms 492 KB Output isn't correct

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

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

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Incorrect 1 ms 492 KB Output isn't correct

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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