Submission #311765

#	Time	Username	Problem	Language	Result	Execution time	Memory
311765		neki	Maja (COCI18_maja)	C++14	55 / 110	6 ms	776 KiB

maja

#include <bits/stdc++.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 110
#define pa pair<ll, ll>
#define ld long double
ll arr[mn][mn], vis[mn][mn], dp[mn][mn], dist[mn][mn];
int main(){
    ll n, m, a, b, k;cin >> n >> m>> a >> b >> k;
    loop(i, 0, n+2){
        loop(j, 0, m+2) arr[i][j]=llmin;
    }
    loop(i, 1, n+1){
        loop(j, 1, m+1){
            cin >> arr[i][j];
        }
    }
    queue<pa> q;q.push(make_pair(a, b));vis[a][b]=1;
    while(q.size()){
        pa u=q.front();q.pop();
        ll x, y;
        x=u.fi+1, y=u.se; if(x>=0 and x<=n and y>=0 and y<=m and !vis[x][y]) vis[x][y]=1, dist[x][y]=dist[u.fi][u.se]+1, q.push(make_pair(x, y));
        if(dist[x][y]==dist[u.fi][u.se]+1) dp[x][y]=max(dp[x][y], dp[u.fi][u.se]+arr[x][y]);
        x=u.fi-1, y=u.se; if(x>=0 and x<=n and y>=0 and y<=m and !vis[x][y]) vis[x][y]=1, dist[x][y]=dist[u.fi][u.se]+1, q.push(make_pair(x, y));
        if(dist[x][y]==dist[u.fi][u.se]+1) dp[x][y]=max(dp[x][y], dp[u.fi][u.se]+arr[x][y]);
        x=u.fi, y=u.se+1; if(x>=0 and x<=n and y>=0 and y<=m and !vis[x][y]) vis[x][y]=1, dist[x][y]=dist[u.fi][u.se]+1, q.push(make_pair(x, y));
        if(dist[x][y]==dist[u.fi][u.se]+1) dp[x][y]=max(dp[x][y], dp[u.fi][u.se]+arr[x][y]);
        x=u.fi, y=u.se-1; if(x>=0 and x<=n and y>=0 and y<=m and !vis[x][y]) vis[x][y]=1, dist[x][y]=dist[u.fi][u.se]+1, q.push(make_pair(x, y));
        if(dist[x][y]==dist[u.fi][u.se]+1) dp[x][y]=max(dp[x][y], dp[u.fi][u.se]+arr[x][y]);
    }
    ll ans=0;
    loop(i, 1, n+1){
        loop(j, 1, m+1){
            
            ll te=k-dist[i][j] * 2;
            ll what=max(arr[i+1][j], max(arr[i-1][j], max(arr[i][j+1], arr[i][j-1])));
            te/=2;
            if(te>=1)ans=max(ans, dp[i][j] * 2 +te * what + (te-1) * arr[i][j]);
        }
    }
    cout << ans << endl;
}

• 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