Submission #990113

#TimeUsernameProblemLanguageResultExecution timeMemory
990113LOLOLOMaja (COCI18_maja)C++17
0 / 110
17 ms65536 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 1e2 + 10; ll mat[N][N], sum[N][N], dp[N * N][N][N]; ll solve() { ll k; int n, m, a, b; cin >> n >> m >> a >> b >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> mat[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { sum[i][j] = max({mat[i - 1][j], mat[i][j - 1], mat[i + 1][j], mat[i][j + 1]}) + mat[i][j]; } } for (int i = 0; i <= n + 1; i++) { for (int j = 0; j <= m + 1; j++) { dp[0][i][j] = -4e17; } } dp[0][a][b] = mat[a][b] * 2; ll sz = n * m; for (int id = 1; id <= sz; id++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[id][i][j] = max({dp[id - 1][i - 1][j], dp[id - 1][i][j - 1], dp[id - 1][i + 1][j], dp[id - 1][i][j + 1]}) + mat[i][j] * 2; } } } ll ans = 0; k++; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { ll x = 0; ll odd = -5e17, even = -5e17; for (ll f = min(sz, k); f >= 1; f--) { while (x <= sz && x + f <= k) { if (x % 2) { odd = max(odd, dp[x][i][j] - x * sum[i][j]); } else { even = max(even, dp[x][i][j] - x * sum[i][j]); } x++; } int t = (k - f) % 2; if (t % 2) { ans = max(ans, dp[f][i][j] - f * sum[i][j] + odd - mat[i][j] * 2 + sum[i][j] * k); } else { ans = max(ans, dp[f][i][j] - f * sum[i][j] + even - mat[i][j] * 2 + sum[i][j] * k); } } } } return ans / 2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { cout << solve() << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...