oj.uz

Submission #522434

# Submission time Handle Problem Language Result Execution time Memory
522434 2022-02-05T03:17:08 Z KoD Maja (COCI18_maja) C++17
110 / 110
 503 ms 532 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;  
    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.0 / 11.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 204 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 3 ms 204 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 332 KB Output is correct
2 Correct 10 ms 292 KB Output is correct
3 Correct 225 ms 532 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 320 KB Output is correct
2 Correct 425 ms 440 KB Output is correct
3 Correct 219 ms 532 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 384 KB Output is correct
2 Correct 503 ms 460 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 332 KB Output is correct
2 Correct 98 ms 336 KB Output is correct

Subtask #9
11.0 / 11.0

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

Subtask #10
11.0 / 11.0

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