Geome try/codechef MCO16204
Материал из DISCOPAL
#include <bits/stdc++.h> int main() { size_t cnt = 0; std::cin >> cnt; std::vector<int64_t> lst(cnt), rst(cnt); for (auto it = lst.rbegin(); it != lst.rend(); ++it) { std::cin >> *it; } for (auto it = rst.rbegin(); it != rst.rend(); ++it) { std::cin >> *it; } auto dim = cnt + 1; std::vector<int64_t> dp_ans(dim * dim); dp_ans[0 * dim + 0] = 0; for (size_t i = 1; i < dim; ++i) { dp_ans[i * dim + 0] = lst[i - 1] - dp_ans[(i - 1) * dim + 0]; dp_ans[0 * dim + i] = rst[i - 1] - dp_ans[0 * dim + (i - 1)]; } for (size_t l = 1; l < dim; ++l) { for (size_t r = 1; r < dim; ++r) { dp_ans[l * dim + r] = std::max(lst[l - 1] - dp_ans[(l - 1) * dim + r], rst[r - 1] - dp_ans[l * dim + (r - 1)]); } } std::cout << dp_ans.back() << '\n'; return 0; } /* import numpy as np if __name__ == '__main__': cnt = int(input()) lst = np.fromiter(map(int, input().split()), dtype=np.int64)[::-1] rst = np.fromiter(map(int, input().split()), dtype=np.int64)[::-1] dim = cnt + 1 dp_ans = np.zeros(dim * dim, dtype=np.int64) dp_ans[0 * dim + 0] = 0 for l in range(1, dim): dp_ans[l * dim + 0] = lst[l - 1] - dp_ans[(l - 1) * dim + 0] for r in range(1, dim): dp_ans[0 * dim + r] = rst[r - 1] - dp_ans[0 * dim + (r - 1)] for l in range(1, dim): for r in range(1, dim): dp_ans[l * dim + r] = max(lst[l - 1] - dp_ans[(l - 1) * dim + r], \ rst[r - 1] - dp_ans[l * dim + (r - 1)]) print(dp_ans[cnt * dim + cnt]) */
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.