oj.uz

Submission #200085

# Submission time Handle Problem Language Result Execution time Memory
200085 2020-02-05T10:15:09 Z Saboon Maja (COCI18_maja) C++14
110 / 110
 163 ms 640 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 105;
int c[maxn][maxn];
ll dp[2][maxn][maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int n, m, k, a, b;
    cin >> n >> m >> a >> b >> k;
	for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
			cin >> c[i][j];

 	ll answer = 0;
    memset(dp, -63, sizeof dp);
    dp[0][a][b] = 0;
	for (int len = 1; len <= n * m && len * 2 <= k; len ++){
        int w = len & 1;
		for (int i = 1; i <= n; i++){
            for (int j = (a + b + i + (!w)) % 2 + 1; j <= m; j += 2){
                dp[w][i][j] = max({dp[!w][i-1][j] + c[i-1][j], dp[!w][i+1][j] + c[i+1][j],
                                  dp[!w][i][j-1] + c[i][j-1], dp[!w][i][j+1] + c[i][j+1]});
 
                int sum = c[i][j] + max({c[i-1][j], c[i+1][j], c[i][j-1], c[i][j+1]});
                answer = max(answer, dp[w][i][j] * 2LL + ((k >> 1) - len) * 1LL * sum + c[i][j]);
            }
		}
    }
	cout << answer << '\n';
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 508 KB Output is correct
2 Correct 89 ms 640 KB Output is correct
3 Correct 163 ms 632 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 632 KB Output is correct
2 Correct 120 ms 632 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 504 KB Output is correct
2 Correct 13 ms 504 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 6 ms 508 KB Output is correct

Subtask #10
11.0 / 11.0

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