제출 #1203196

#제출 시각아이디문제언어결과실행 시간메모리
1203196kevinyangSafety (NOI18_safety)C++20
100 / 100
115 ms20744 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; struct Slope{ multiset<int>l; multiset<int>r; int b = 0; int delta = 0; void balance(){ while(l.size() < r.size()){ int fst = *r.begin() + delta; r.erase(r.begin()); l.insert(fst); } while(l.size() > r.size()){ int lst = *--l.end(); r.insert(lst-delta); l.erase(--l.end()); } } void shiftmin(int x){ balance(); delta += x; } void add(int x){ // multiset insert x two times b += x; if(l.size() && *--l.end() >= x){ l.insert(x); l.insert(x); } else{ r.insert(x-delta); r.insert(x-delta); } balance(); } int evalmn(){ balance(); int cur = 0; int y = b; int m = -l.size(); for(int nxt: l){ y += m * (nxt-cur); cur = nxt; m++; } return y; } }; signed main() { cin.tie(0)->sync_with_stdio(0); int n,h; cin >> n >> h; vector<int>a(n+1); for(int i = 1; i<=n; i++){ cin >> a[i]; a[i] += i*h; } Slope s; for(int i = 1; i<=n; i++){ if(i>1){ s.shiftmin(2*h); } s.add(a[i]); } cout << s.evalmn() << '\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...
#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...