Submission #1090729

#TimeUsernameProblemLanguageResultExecution timeMemory
1090729vjudge1Safety (NOI18_safety)C++17
100 / 100
239 ms21076 KiB
#include <cassert> #include <iostream> #include <set> int main() { std::cin.tie(NULL)->sync_with_stdio(false); int n; long long h; std::cin >> n >> h; int m = 0; long long shift = -h, c = 0; std::multiset<long long> m_changes[2]; // xpos for each m changes +1 for (int i = 0; i < n; i++) { long long x; std::cin >> x; // shift by h shift += h; c -= h * m; // append to line m_changes[0].insert(x + shift); m_changes[1].insert(x - shift); // normalize while (true) { long long x_l = *m_changes[0].rbegin(); long long x_r = *m_changes[1].begin(); if (x_l - shift <= x_r + shift) { break; } m_changes[0].erase(m_changes[0].find(x_l)); m_changes[1].erase(m_changes[1].find(x_r)); x_l -= shift; x_r += shift; m_changes[0].insert(x_r + shift); m_changes[1].insert(x_l - shift); } // m*x + c + (x - x0) = (m+1)*x + (c - x0) m++; c -= x; } while (!m_changes[1].empty()) { // pop largest long long x = *m_changes[1].rbegin(); m_changes[1].erase(m_changes[1].find(x)); // apply shift x += shift; assert(x >= 0); // m*x + c = (m-1)*x + (x + c) m--; c += x; } assert(m == 0); 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...