oj.uz

Submission #92161

# Submission time Handle Problem Language Result Execution time Memory
92161 2019-01-01T19:14:40 Z Kastanda Maja (COCI18_maja) C++11
110 / 110
 111 ms 636 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m, k, a, b, A[N][N];
long long MX, dp[2][N][N];
int main()
{
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &A[i][j]);

    memset(dp, -63, sizeof(dp));
    dp[0][a][b] = 0;
    for (int len = 1, w = 1; len <= n * m && len * 2 <= k; len ++, w = !w)
    {
        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] + A[i-1][j], dp[!w][i+1][j] + A[i+1][j],
                                  dp[!w][i][j-1] + A[i][j-1], dp[!w][i][j+1] + A[i][j+1]});

                int sum = A[i][j] + max({A[i-1][j], A[i+1][j], A[i][j-1], A[i][j+1]});
                MX = max(MX, dp[w][i][j] * 2LL + ((k >> 1) - len) * 1LL * sum + A[i][j]);
            }
    }
    return !printf("%lld\n", MX);
}

Compilation message

maja.cpp: In function 'int main()':
maja.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d", &n, &m, &a, &b, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maja.cpp:11:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

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 508 KB Output is correct

Subtask #2
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 #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 3 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 11 ms 632 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 107 ms 628 KB Output is correct

Subtask #6
11.0 / 11.0

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

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 636 KB Output is correct
2 Correct 86 ms 632 KB Output is correct

Subtask #8
11.0 / 11.0

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

Subtask #9
11.0 / 11.0

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

Subtask #10
11.0 / 11.0

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