제출 #1269420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269420		k12_khoi	Stove (JOI18_stove)	C++17	100 / 100	13 ms	2376 KiB

stove

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,int>
#define X first
#define Y second

const int N=1e5+5;
const int oo=1e9+1;

int n,k;
int a[N];

namespace sub1
{
    int limit,res;
    bool check[N];

    void ql(int i,int used,int sum,bool onFire)
    {
        if (i>limit)
        {
            res=min(res,sum);
            return;
        }

        if (!check[i]) ql(i+1,used,sum,0);

        if (used+(onFire==false)<=k) ql(i+1,used+(onFire==false),sum+1,1);
    }

    void solve()
    {
        limit=a[n];

        for (int i=1;i<=n;i++)
        check[a[i]]=true;

        res=oo;
        ql(1,0,0,0);

        cout << res;
    }
}

namespace sub2
{
    int dp_before[N],dp_cur[N];

    void dnc(int l,int r,int optl,int optr)
    {
        if (l>r) return;

        int mid=(l+r)/2;

        int limit=min(optr,mid);

        pii best=make_pair(oo,0);
        for (int i=optl;i<=limit;i++)
        best=min(best,make_pair((ll)dp_before[i-1]+a[mid]-a[i]+1,-i));

        dp_cur[mid]=best.X;

        int opt=-best.Y;

        dnc(l,mid-1,optl,opt);
        dnc(mid+1,r,opt,optr);
    }

    void solve()
    {
        for (int i=1;i<=n;i++)
        dp_before[i]=a[i]-a[1]+1;

        for (int j=2;j<=k;j++)
        {
            dnc(1,n,1,n);

            for (int i=1;i<=n;i++)
            dp_before[i]=dp_cur[i];
        }

        cout << dp_before[n];
    }
}

namespace sub3
{
    pii cmp_pair(pii x,pii y)
    {
        if (x.X==y.X) return max(x,y);
        return min(x,y);
    }

    ll l,r,mid,res;
    pii dp[N];

    pii check(int lambda)
    {
        dp[1]=make_pair(1+lambda,1);

        for (int i=2;i<=n;i++)
        dp[i]=cmp_pair(make_pair(dp[i-1].X+a[i]-a[i-1],dp[i-1].Y),make_pair(dp[i-1].X+1+lambda,dp[i-1].Y+1));

        return dp[n];
    }

    void solve()
    {
        res=0;
        l=0;
        r=1e9;
        while (l<=r)
        {
            mid=(l+r)/2;
            if (check(mid).Y>=k)
            {
                l=mid+1;
                res=mid;
            }
            else r=mid-1;
        }

        cout << check(res).X-res*k;
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> k;
    for (int i=1;i<=n;i++)
    cin >> a[i];

    sub3::solve();
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50