제출 #336747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336747		monus1042	Maja (COCI18_maja)	C++17	55 / 110	2 ms	492 KiB

maja

// 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;
			stepsrem/=2;
			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];
					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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11