Submission #901287

#TimeUsernameProblemLanguageResultExecution timeMemory
901287nguyen31hoang08minh2003Holding (COCI20_holding)C++14
88 / 110
119 ms262144 KiB
#include <bits/stdc++.h> template<class A, class B> bool maximize(A &a, const B& b) { if (a < b) { a = b; return true; } return false; } template<class A, class B> bool minimize(A &a, const B& b) { if (a > b) { a = b; return true; } return false; } using namespace std; constexpr int MAX_N = 105, MAX_K = 1E4 + 5; constexpr long long INF = 0X3F3F3F3F3F3F3F3F, NINF = 0XC0C0C0C0C0C0C0C0; int N, L, R, K, A[MAX_N]; long long result = INF; /* Consider the problem Give n integers a[1], ..., a[n] and another n integers b[1], ..., b[n] Find permutations of (1, ..., n), p and q such that |a[p[1]] - b[q[1]]| + ... + |a[p[n]] - b[q[n]]| is minimum Solution: Sort a and b If we want to bring m elements whose indices greater than R into range [L, R] then we should allocate them in range [R - m + 1, R] If we want to bring m elements whose indices smaller than L into range [L, R] then we should allocate them in range [L, L + m - 1] */ long long findRightOptimalCost(const int i, const int j, const int k) { static long long minimum[MAX_N][MAX_N][MAX_K]; static bool visited[MAX_N][MAX_N][MAX_K]; if (k < 0 || j > N + 1) return INF; if (i > R) return 0; if (!visited[i][j][k]) { visited[i][j][k] = true; minimum[i][j][k] = findRightOptimalCost(i + 1, j, k) + A[i]; if (j <= N) { const int d = j - i; minimize(minimum[i][j][k], findRightOptimalCost(i, j + 1, k)); if (k >= d) minimize(minimum[i][j][k], findRightOptimalCost(i + 1, j + 1, k - d) + A[j]); } } return minimum[i][j][k]; } long long findLeftOptimalCost(const int i, const int j, const int k) { static long long minimum[MAX_N][MAX_N][MAX_K]; static bool visited[MAX_N][MAX_N][MAX_K]; if (k < 0 || j < 0) return INF; if (i < L) return 0; if (!visited[i][j][k]) { visited[i][j][k] = true; minimum[i][j][k] = findLeftOptimalCost(i - 1, j, k) + A[i]; if (j >= 1) { const int d = i - j; minimize(minimum[i][j][k], findLeftOptimalCost(i, j - 1, k)); if (k >= d) minimize(minimum[i][j][k], findLeftOptimalCost(i - 1, j - 1, k - d) + A[j]); } } return minimum[i][j][k]; } signed main() { #ifdef LOCAL freopen("input.INP", "r", stdin); #endif // LOCAL cin.tie(0) -> sync_with_stdio(0); cout.tie(0); cin >> N >> L >> R >> K; for (int i = 1; i <= N; ++i) cin >> A[i]; minimize(result, min(findLeftOptimalCost(R, L - 1, K), findRightOptimalCost(L, R + 1, K))); for (int i = L, k; i < R; ++i) for (k = 0; k <= K; ++k) minimize(result, findLeftOptimalCost(i, L - 1, k) + findRightOptimalCost(i + 1, R + 1, K - k)); cout << result << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...