oj.uz

답안 #1105094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105094 2024-10-25T10:43:34 Z Faggi Sails (IOI07_sails) C++11
0 / 100
 216 ms 9228 KB 
#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;    priority_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.top().first;        sob+=sum.top().second;        sum.pop();        while(res.size()&&res.top().first>pos)            res.pop();        while(res.size()&&sob>0)        {            sob-=res.top().second;            posR=res.top().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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 0 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 2344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 2832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 4272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 216 ms 9228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 180 ms 9044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 200 ms 8248 KB Output isn't correct
2 Halted 0 ms 0 KB -