Submission #903980

#TimeUsernameProblemLanguageResultExecution timeMemory
903980nguyen31hoang08minh2003Holding (COCI20_holding)C++14
110 / 110
44 ms10740 KiB
#include <bits/stdc++.h> /* 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 Thus, the elements which are originally to the left of the interval [L, R] should have final positions to the left to final positions of the elements which are originally to the right of the interval [L, R] */ 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 = 102, MAX_K = 1E4 + 4, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0; int result = INF, N, L, R, K, A[MAX_N], leftCost[MAX_N][MAX_K], rightCost[MAX_N][MAX_K], newCost[MAX_N][MAX_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]; for (int j = 0, i, k, d; j < L; ++j) { for (i = L; i <= R; ++i) for (k = 0; k <= K; ++k) { newCost[i][k] = newCost[i - 1][k] + A[i]; if (j >= 1) { d = i - j; minimize(newCost[i][k], leftCost[i][k]); if (k >= d) minimize(newCost[i][k], leftCost[i - 1][k - d] + A[j]); } } for (i = L; i <= R; ++i) for (k = 0; k <= K; ++k) leftCost[i][k] = newCost[i][k]; } for (int j = N + 1, i, k, d; j > R; --j) { for (i = R; i >= L; --i) for (k = 0; k <= K; ++k) { newCost[i][k] = newCost[i + 1][k] + A[i]; if (j <= N) { d = j - i; minimize(newCost[i][k], rightCost[i][k]); if (k >= d) minimize(newCost[i][k], rightCost[i + 1][k - d] + A[j]); } } for (i = R; i >= L; --i) for (k = 0; k <= K; ++k) rightCost[i][k] = newCost[i][k]; } minimize(result, min(leftCost[R][K], rightCost[L][K])); for (int i = L, k; i < R; ++i) for (k = 0; k <= K; ++k) minimize(result, leftCost[i][k] + rightCost[i + 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...