oj.uz

Submission #95408

# Submission time Handle Problem Language Result Execution time Memory
95408 2019-01-31T16:39:53 Z dalgerok Maja (COCI18_maja) C++14
110 / 110
 401 ms 760 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;




const int N = 105, INF = 1e18, dx[] = {0, -1, 0, 1},
dy[] = {-1, 0, 1, 0};




int n, m, a, b, len, A[N][N], dp[2][N][N], ans;


inline void upd(int &x, int y){
    if(x < y){
        x = y;
    }
}

inline bool check(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> a >> b >> len;
    len /= 2;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> A[i][j];
        }
    }
    memset(dp, -63, sizeof(dp));
    dp[0][a][b] = 0;
    int p = min(len, n * m);
    for(int i = 1; i <= p; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= m; k++){
                dp[i & 1][j][k] = -INF;
            }
        }
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= m; k++){
                if(dp[(i - 1) & 1][j][k] >= 0){
                    for(int l = 0; l < 4; l++){
                        int x = j + dx[l], y = k + dy[l];
                        if(check(x, y)){
                            upd(dp[i & 1][x][y], dp[(i - 1) & 1][j][k] + A[x][y]);
                        }
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int val = 2 * dp[p & 1][i][j] - A[i][j];
            int mx = 0;
            for(int l = 0; l < 4; l++){
                int x = i + dx[l], y = j + dy[l];
                if(check(x, y)){
                    upd(mx, A[x][y]);
                }
            }
            mx += A[i][j];
            mx = mx * max(0LL, len - n * m);
            ans = max(ans, mx + val);
        }
    }
    cout << ans;
}



/**
2 2 1 1 2
0 1
2 10
*/

Compilation message

maja.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 600 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 360 ms 760 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 296 ms 760 KB Output is correct
3 Correct 361 ms 632 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 676 KB Output is correct
2 Correct 401 ms 700 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 504 KB Output is correct
2 Correct 29 ms 632 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct