Submission #638324

#TimeUsernameProblemLanguageResultExecution timeMemory
6383244EVERMaja (COCI18_maja)C++11
110 / 110
399 ms588 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("O2") //#pragma GCC target("avx,avx2,fma") using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define PB push_back #define ALL(i_) i_.begin(), i_.end() #define LOG2(x) (31 - __builtin_clz(x)) #define getBit(x, i) ((x >> i) & 1) #define rd(l, r) (l + rng() % (r - l + 1)) typedef long long ll; typedef long double ld; typedef pair<int, int> ii; template<class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) { x = y; return 1; } return 0; } template<class X, class Y> bool maximize(X &x, const Y &y) { X eps = 1e-9; if (x + eps < y) { x = y; return 1; } return 0; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); } const int mod = (int) 1e9 + 7; const int oo = (int) 1e9 + 99; const int maxn = (int) 1e5 + 11; const int LOG = (int) 20; const ii dxy[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} }; int n, m, k, sta_x, sta_y; int a[101][101]; ll dp[2][101][101]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define TASK "MAJA" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } cin >> n >> m >> sta_x >> sta_y >> k; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> a[i][j]; memset(dp, -1, sizeof dp); dp[0][sta_x][sta_y] = 0; k >>= 1; int step = min(k, n * m); for(int t = 0; t < step; t++){ int cur = t & 1; int nxt = !cur; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) if(dp[cur][i][j] != -1){ for(int d = 0; d < 4; d++){ int u = i + dxy[d].first; int v = j + dxy[d].second; if(u >= 1 && u <= n && v >= 1 && v <= m){ maximize(dp[nxt][u][v], dp[cur][i][j] + a[u][v]); } } } } memset(dp[cur], -1, sizeof dp[cur]); } ll res = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ int rem = k - step; for(int d = 0; d < 4; d++){ int u = i + dxy[d].first; int v = j + dxy[d].second; if(u >= 1 && u <= n && v >= 1 && v <= m){ ll val = a[i][j] + a[u][v]; maximize(res, 2ll * dp[step & 1][i][j] + 1ll * rem * val - a[i][j]); } } } } cout << res; return 0; }

Compilation message (stderr)

maja.cpp: In function 'int main()':
maja.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
maja.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...