| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1339128 | po_rag526 | Sails (IOI07_sails) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<ll,ll>
#define F first
#define S second
#define LOO(i,a,b) for (ll i = a; i<=b; i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define OOL(i,a,b) for (ll i = b; i >=a; i--)
vector<pii> cool;
void solve() {
LOO(i,0,1e5) ttl[i]=0;
int n;
cin>>n;
cool = vector<pii>(n);
LOO(i,0,n-1)cin>>cool[i].F>>cool[i].S;
int currp = 0;
sort(all(cool));
ll l = 0;
ll r = 1e9;
while (r>l) {
ll mid=(l+r)/2;
bool ispossible = true;
currp=0;
vector<ll> ttl(1'000'01);
LOO(i,0,n-1) {
ll left = cool[i].S;
while (left) {
ttl[currp]+=min(mid,left);
left-=min(mid,left);
if (ttl[currp]==mid) currp++;
}
if (currp>=cool[i].F) {
ispossible=false;
break;
}
}
if (ispossible) r =mid;
else l =mid+1;
}
currp=0;
vector<ll> ttl(1'000'01);
ll answer = 0;
LOO(i,0,n-1) {
ll left = cool[i].S;
while (left) {
ttl[currp]+=min(l,left);
left-=min(l,left);
if (ttl[currp]==l) currp++;
}
}
for (ll ele: ttl) answer+=ele*(ele-1)/2;
cout << answer << '\n';
}
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
while (t--) solve();
}