Submission #986588

#TimeUsernameProblemLanguageResultExecution timeMemory
986588AverageAmogusEnjoyerSails (IOI07_sails)C++17
10 / 100
13 ms2908 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 solve(ll k) { copy(a,a+nax,b); ll ans = 0; for (int i=nax-1;i>=1;i--) { ll to_do = min(k,b[i]); ans += to_do*(to_do-1)/2; b[i]-=to_do; b[i-1]+=b[i]; } if (b[0] != 0) { return 1LL<<60; } return ans; } 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 = 1e6; while(lo < hi) { ll mid = lo+(hi-lo+1)/2; if (mid*mid <= sum) { lo = mid; } else { hi = mid-1; } } cout << min(solve(lo),solve(lo+1)) << 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...