Submission #522434

#	Time	Username	Problem	Language	Result	Execution time	Memory
522434		KoD	Maja (COCI18_maja)	C++17	110 / 110	503 ms	532 KiB

maja

#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;  
    const auto try_loop = [&](const int u, const int v) {
        setmax(ans, dp[u] * 2 + (i64)(C[u] + C[v]) * (K - L + 1) - C[u] - C[u] - C[v]);
    };
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            const int u = i * M + j;
            if (i != 0) try_loop(u, u - M);
            if (i != N - 1) try_loop(u, u + M);
            if (j != 0) try_loop(u, u - 1);
            if (j != M - 1) try_loop(u, u + 1);
        }
    }
    std::cout << ans << '\n';
    return 0;
}

• 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