#include <bits/stdc++.h>
using namespace std;
using lint = long long;
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;
}
}
int 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';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
860 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
1368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
1484 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
1996 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
2104 KB |
Output is correct |
2 |
Correct |
34 ms |
1936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
54 ms |
2244 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |