Submission #200085

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
200085	2020-02-05 10:15:09	Saboon	Maja (COCI18_maja)	C++14	110 / 110	163 ms	640 KiB

maja

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]);
            }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• 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