Submission #743284

#	Time	Username	Problem	Language	Result	Execution time	Memory
743284		Prieved1	Safety (NOI18_safety)	C++17	100 / 100	63 ms	6984 KiB

safety

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  ll h;
  cin >> n >> h;
  ll s[n];
  priority_queue<ll> lf;
  priority_queue<ll, vector<ll>, greater<ll>> rt;
  long long res=0;
  for(int i = 0;i<n;i++) {
    cin >> s[i];
    if(i==0) {
      lf.push(s[i]);
      rt.push(s[i]);
      continue;
    }
    long long c=i*h;
    if(s[i]<=lf.top()-c) {
      lf.push(s[i]+c);
      lf.push(s[i]+c);
      res+=abs(lf.top()-(s[i]+c));
      rt.push(lf.top()-2*c);
      lf.pop();
    }
    else if(s[i]>=rt.top()+c) {
      rt.push(s[i]-c);
      rt.push(s[i]-c);
      res+=abs(rt.top()-(s[i]-c));
      lf.push(rt.top()+2*c);
      rt.pop();
    }
    else {
     lf.push(s[i]+c);
     rt.push(s[i]-c);
    }
  }
  cout << res << "\n";
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29