oj.uz

Submission #522433

# Submission time Handle Problem Language Result Execution time Memory
522433 2022-02-05T03:08:03 Z KoD Maja (COCI18_maja) C++17
44 / 110
 393 ms 436 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::tuple;
using std::pair;

using i64 = std::int64_t;

constexpr i64 INF = std::numeric_limits<i64>::max() / 2;

template <class T> void setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M, sx, sy, K;
    std::cin >> N >> M >> sx >> sy >> K;
    sx -= 1, sy -= 1;
    K /= 2;
    const int V = N * M;
    vector<int> C(V);
    for (auto& x : C) {
        std::cin >> x;
    }
    vector<i64> dp(V, -INF), next(V);
    dp[sx * M + sy] = 0;
    const auto transit = [&] {
        std::fill(next.begin(), next.end(), -INF);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                const int u = i * M + j;
                if (i != 0) setmax(next[u], dp[u - M] + C[u]);
                if (i != N - 1) setmax(next[u], dp[u + M] + C[u]);
                if (j != 0) setmax(next[u], dp[u - 1] + C[u]);
                if (j != M - 1) setmax(next[u], dp[u + 1] + C[u]);
            }
        }
        std::swap(dp, next);
    };
    if (K <= 10000) {
        for (int k = 0; k < K; ++k) {
            transit();
        }
        i64 ans = -INF;
        for (int i = 0; i < V; ++i) {
            setmax(ans, dp[i] * 2 - C[i]);
        }
        std::cout << ans << '\n';
        return 0;
    }
    const int L = 10000 + (K % 2 == 0);
    for (int k = 0; k < L; ++k) {
        transit();
    }      
    i64 ans = 0;  
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            const int u = i * M + j;
            int sum = 0;
            if (i != 0) setmax(sum, C[u - M]);
            if (i != N - 1) setmax(sum, C[u + M]);
            if (j != 0) setmax(sum, C[u - 1]);
            if (j != M - 1) setmax(sum, C[u + 1]);
            sum += C[u];
            const i64 get = dp[u] + (i64)sum * (K - L + 1) / 2;
            setmax(ans, (get - C[u]) * 2);
        }
    }
    std::cout << ans << '\n';
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 320 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 393 ms 436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -