Submission #1339138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339138		po_rag526	Sails (IOI07_sails)	C++20	0 / 100	33 ms	2772 KiB

sails

#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() {
    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) {
                ll vv = min(mid-ttl[currp],left);
                ttl[currp]+=vv;
                left-=min(vv,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;
    vector<bool> doubleback(1'000'01,false);
    l--;
    int otherp = 0;
    LOO(i,0,n-1) {
        ll left = cool[i].S;
        while (left && currp!=cool[i].F) {
            ll vv = min(l-ttl[currp],left);
            ttl[currp]+=vv;
            left-=min(vv,left);
            if (ttl[currp]==l) currp++;
        }
        while (left) {
            left--;
            ttl[otherp]++;
            otherp++;
        }
    }
    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();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10