Submission #1104987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104987		Faggi	Sails (IOI07_sails)	C++11	25 / 100	19 ms	6224 KiB

sails

#include <bits/stdc++.h>
#define ll long long
using namespace std;vector<ll>tamDP;vector<ll>calcs;ll tam;bool can(vector<ll> dp,ll x){    ll ma, sob, i;    for(i=tam; i>0ll; i--)    {        ma=min(x,tamDP[i]);        sob=0ll;        if(dp[i]>ma)        {            sob=dp[i]-ma;            dp[i]=ma;            if(i>1ll)                dp[i-1ll]+=sob;            else                return 0;        }    }    return 1;}ll calc(vector<ll> dp, ll x){    ll ma, sob, i, res=0ll;    for(i=tam; i>0ll; i--)    {        ma=min(x,tamDP[i]);        sob=0ll;        if(dp[i]>ma)        {            sob=dp[i]-ma;            dp[i]=ma;            dp[i-1ll]+=sob;        }    }    for(i=tam; i>0ll; i--)    {        res+=calcs[dp[i]];    }    return res;}int main(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    ll n, i, mi=0ll, ma=0ll, piv,pos;    cin >> n;    calcs.resize(n+1ll);    calcs[0ll]=0ll;    calcs[1ll]=0ll;    for(i=2ll; i<=n; i++)    {        calcs[i]+=calcs[i-1ll]+(i-1ll);    }    vector<pair<ll,ll>>v(n);    for(i=0ll; i<n; i++)    {        cin >> v[i].first >> v[i].second;        tam=max(v[i].first,tam);    }    vector<ll> dp(tam+1,0ll);    tamDP.resize(tam+1,0ll);    for(i=0ll; i<n; i++)    {        dp[v[i].first]+=1ll;        dp[v[i].first-v[i].second]-=1ll;        tamDP[v[i].first]+=1ll;    }    ma=dp[tam];    for(i=tam-1ll; i>=0ll; i--)    {        dp[i]+=dp[i+1ll];        ma=max(ma,dp[i]);        tamDP[i]+=tamDP[i+1ll];    }    pos=ma;    while(mi<=ma)    {        piv=(mi+ma)/2ll;        if(can(dp,piv))        {            ma=piv-1ll;            pos=piv;        }        else        {            mi=piv+1ll;        }    }    cout << calc(dp,pos) << '\n';    return 0;}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 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