Submission #1054509

#TimeUsernameProblemLanguageResultExecution timeMemory
1054509unnickSafety (NOI18_safety)C++14
9 / 100
2099 ms262144 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int ll; int main() { int n, h; cin >> n >> h; if (h == 0) { vector<int> a; ll sum = 0; for (int i = 0; i < n; i++) { int tmp; cin >> tmp; a.push_back(tmp); } sort(a.begin(), a.end()); int p = a[a.size() / 2]; for (auto v : a) { sum += abs(v-p); } cout << sum << "\n"; return 0; } vector<int> a(n); int q = 0; for (int i = 0; i < n; i++) { cin >> a[i]; q = max(q, a[i]); } q++; vector<ll> aa(q); vector<ll> ab(q); for (int i = 0; i < q; i++) { aa[i] = abs(a[0]-i); } for (int j = 1; j < n; j++) { for (int i = 0; i < q; i++) { ll tmp = 0x7FFFFFFFFFFFFFFFLL; for (int o = -h; o <= h; o++) { if (i+o >= 0 && i+o < q) tmp = min(tmp, aa[i+o]); } ab[i] = tmp + abs(i - a[j]); } aa.swap(ab); } ll sol = 0x7FFFFFFFFFFFFFFFLL; for (int i = 0; i < q; i++) sol = min(sol, aa[i]); cout << sol << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...