Submission #95408

#	Time	Username	Problem	Language	Result	Execution time	Memory
95408		dalgerok	Maja (COCI18_maja)	C++14	110 / 110	401 ms	760 KiB

maja

#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 (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11