제출 #986599

#제출 시각아이디문제언어결과실행 시간메모리
986599AverageAmogusEnjoyerSails (IOI07_sails)C++17
25 / 100
20 ms3164 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> bool cmin(T &i,T j) { return i > j ? i = j,true: false; } template<class T> bool cmax(T &i,T j) { return i < j ? i = j,true: false; } constexpr int nax = 100100; ll a[nax]; ll b[nax]; int n; ll cost; bool can(ll k) { copy(a,a+nax,b); cost = 0; for (int i=nax-1;i>=1;i--) { ll to_do = min(k,b[i]); cost += to_do*(to_do-1)/2; b[i]-=to_do; b[i-1]+=b[i]; } return b[0] == 0LL; } void solve() { cin >> n; ll sum = 0; for (int i=0,h,k;i<n;i++) { cin >> h >> k; a[h]++; a[h-k]--; sum += k; } for (int i=nax-1;i>=1;i--) { a[i-1]+=a[i]; } ll lo = 0, hi = sum; while(lo < hi) { ll mid = lo+(hi-lo)/2; if (!can(mid)) { lo = mid+1; } else { hi = mid; } } assert(can(lo)); cout << cost << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; while(t--) { solve(); } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...