Submission #987224

#TimeUsernameProblemLanguageResultExecution timeMemory
987224GhettoSails (IOI07_sails)C++17
55 / 100
48 ms3012 KiB
#include <bits/stdc++.h> using namespace std; using lint = long long; #define int lint const int MAX_H = 1e5 + 5; const lint INF = 3e18; int n; vector<int> hs; lint s; int w[MAX_H]; void precomp() { for (int h = 1; h <= 1e5; h++) { int i = lower_bound(hs.begin(), hs.end(), h) - hs.begin(); w[h] = n - i; } } signed main() { // freopen("sails.in", "r", stdin), freopen("sails.out", "w", stdout); cin >> n; for (int i = 1; i <= n; i++) { int h; cin >> h; hs.push_back(h); lint new_s; cin >> new_s; s += new_s; } sort(hs.begin(), hs.end()); precomp(); auto consec_sum = [] (lint x) { return x * (x + 1) / 2; }; lint ans = INF, sum = 0; for (int h = 1e5; h >= 1; h--) { if (s <= h * (lint) w[h]) { lint new_ans = sum + h * consec_sum(s / h - 1) + (s / h) * (s % h); ans = min(ans, new_ans); } s -= w[h], sum += consec_sum(w[h] - 1); if (s < 0) break; } cout << ans << '\n'; }
#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...