This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |