oj.uz

Submission #311765

# Submission time Handle Problem Language Result Execution time Memory
311765 2020-10-11T14:13:33 Z neki Maja (COCI18_maja) C++14
55 / 110
 6 ms 776 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 6 ms 776 KB Output isn't correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Incorrect 2 ms 640 KB Output isn't correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -