Submission #1105093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105093		Faggi	Sails (IOI07_sails)	C++11	0 / 100	67 ms	6728 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=0, i,pos,posR;    queue<pair<ll,ll>>sum,res;    for(i=tam; i>0ll; i--)    {        ma=min(x,tamDP[i]);        if(dp[i]>ma)        {            sob=dp[i]-ma;            dp[i]=ma;            if(i>1ll)                sum.push({i,sob});            else                return 0;        }        else        {            res.push({i,ma-dp[i]});        }    }    while(sum.size()&&res.size())    {        pos=sum.front().first;        sob+=sum.front().second;        sum.pop();        while(res.size()&&res.front().first>pos)            res.pop();        while(res.size()&&sob>0)        {            sob-=res.front().second;            posR=res.front().first;            res.pop();        }        if(sob>0)            return 0;        else        {            res.push({posR,abs(sob)});            sob=0;        }    }    if(sum.size()||sob>0)        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(){    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) << endl;    return 0;}

• 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