Submission #1090870

#TimeUsernameProblemLanguageResultExecution timeMemory
1090870vjudge1Safety (NOI18_safety)C++17
100 / 100
73 ms3792 KiB
#include <functional> #include <iostream> #include <queue> #include <vector> int main() { std::cin.tie(NULL)->sync_with_stdio(false); int n; long long h; std::cin >> n >> h; // dp[0][x]: y = |x - a[0]| // dp[i+1][x] = min(dp[i][y], x - h <= y <= x + h) + |x - a[i+1]| // inductively: dp[i] is a convex linear piecewise lines // min x-h <= y <= x+h --> shift minimum range (xL, xR) -> (xL - h, xR + h) int m = 0; long long shift = -h, c = 0; std::priority_queue<long long> pq_l; std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq_r; for (int i = 0; i < n; i++) { long long x; std::cin >> x; // shift by h shift += h; c -= h * m; // append to line pq_l.push(x + shift); pq_r.push(x - shift); // normalize while (true) { long long x_l = pq_l.top(); long long x_r = pq_r.top(); if (x_l - shift <= x_r + shift) { break; } pq_l.pop(); pq_r.pop(); x_l -= shift; x_r += shift; pq_l.push(x_r + shift); pq_r.push(x_l - shift); } // m*x + c + (x - x0) = (m+1)*x + (c - x0) m++; c -= x; } while (!pq_r.empty()) { // pop largest long long x = pq_r.top(); pq_r.pop(); // apply shift x += shift; // m*x + c = (m-1)*x + (x + c) m--; c += x; } std::cout << c << std::endl; 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...
#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...