Submission #90498

#TimeUsernameProblemLanguageResultExecution timeMemory
90498psmaoMaja (COCI18_maja)C++14
0 / 110
3 ms756 KiB
#include <bits/stdc++.h> using namespace std; #define fo(i,s,t) for(int i = s; i <= t; ++ i) #define fd(i,s,t) for(int i = s; i >= t; -- i) #define bf(i,s) for(int i = head[s]; i; i = e[i].next) #define mp make_pair #define fi first #define se second #define pii pair<int,int> #define pb push_back #define VI vector<int> #define sf scanf #define pf printf #define fp freopen #define SZ(x) ((int)(x).size()) #ifdef MPS #define D(x...) printf(x) #else #define D(x...) #endif typedef long long ll; typedef double db; typedef unsigned long long ull; const int inf = 1<<30; const ll INF = 1ll<<60; const db Inf = 1e20; const db eps = 1e-9; void gmax(int &a,int b){a = (a > b ? a : b);} void gmin(int &a,int b){a = (a < b ? a : b);} const int maxn = 105; const int dx[] = {0, 0, 1, -1}; const int dy[] = {-1, 1, 0, 0}; int n, m, A[maxn][maxn], d[maxn][maxn], P[maxn][maxn], a, b, K; ll V[maxn][maxn], Ans; vector<pii> candi; bool cmp(pii a, pii b){return d[a.fi][a.se] < d[b.fi][b.se];} int main() { #ifdef MPS fp("1.in","r",stdin); fp("1.out","w",stdout); #endif sf("%d%d%d%d%d",&n,&m,&a,&b,&K); fo(i,1,n) fo(j,1,m) sf("%d",&A[i][j]); fo(i,1,n) fo(j,1,m) fo(k,0,3) P[i][j] = max(P[i][j], A[i][j] + A[i+dx[k]][j+dy[k]]); queue<pii> Q; memset(d,0xff,sizeof(d)); Q.push(mp(a,b)); d[a][b] = 0; while(!Q.empty()) { pii h = Q.front(); Q.pop(); fo(i,0,3) { int nx = h.fi + dx[i], ny = h.se + dy[i]; if(nx < 1 || ny < 1 || nx > n || ny > m) continue; if(d[nx][ny] != -1) continue; d[nx][ny] = d[h.fi][h.se] + 1; Q.push(mp(nx, ny)); } } fo(i,1,n) fo(j,1,m) candi.pb(mp(i,j)), V[i][j] = -INF; V[a][b] = 0; // for(auto p : candi)cout << p.fi << ' ' << p.se << endl; sort(candi.begin(),candi.end(),cmp); for(auto q : candi) { int i = q.fi, j = q.se; continue; fo(k,0,3) { int nx = i + dx[k], ny = j + dy[k]; if(nx < 1 || ny < 1 || nx > n || ny > m || d[nx][ny] + 1 != d[i][j]) continue; V[i][j] = max(V[i][j], V[nx][ny] + A[i][j]); } } Ans = -inf; fo(i,1,n) fo(j,1,m) { int k = K/2-d[i][j]; if(k < 0) continue; Ans = max(Ans, 1ll*k*P[i][j] + V[i][j]*2 - A[i][j]); } cout << Ans << endl; return 0; }

Compilation message (stderr)

maja.cpp: In function 'int main()':
maja.cpp:48:4: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  sf("%d%d%d%d%d",&n,&m,&a,&b,&K);
    ^
maja.cpp:49:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fo(i,1,n) fo(j,1,m) sf("%d",&A[i][j]);
                        ^
#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...