Submission #169085

#	Time	Username	Problem	Language	Result	Execution time	Memory
169085		HuyQuang_re_Zero	Stove (JOI18_stove)	C++14	100 / 100	281 ms	83052 KiB

stove

#include <bits/stdc++.h>
using namespace std;
long long n,m,i,j,k,t[100001],kq,d[1001],f[5001][5001];
void vet(int i,int sl)
{
    if(sl>m) return ;
    if(i>n)
    {
        long long sum=0,vt;
        for(int j=1;j<=n;j++)
        {
            if(d[j]==1) vt=t[j];
            if(j==n || d[j+1]==1) sum+=t[j]+1-vt;
        }
        kq=min(kq,sum);
        return ;
    }
    if(i==1) { d[i]=1; vet(i+1,sl+1); }
    else
    {
        for(int j=0;j<=1;j++)
        {
            d[i]=j;
            vet(i+1,sl+j);
        }
    }
}
void sub1()
{
    kq=round(1e9);
    vet(1,0);
    cout<<kq;
}

//////////////////////////////////////////////////////////////

const long long oo=round(1e18);

void sub2()
{
    for(i=0;i<=n;i++)
        for(k=0;k<=m;k++) f[i][j]=oo;
    f[0][0]=0;
    for(k=1;k<=n;k++)
    {
        long long mi=oo;
        for(i=0;i<=n;i++)
        {
            if(i>0 && mi<oo) f[i][k]=mi+t[i]+1;
            if(i<n && f[i][k-1]<oo) mi=min(mi,f[i][k-1]-t[i+1]);
        }
    }
    cout<<f[n][m];
}

/////////////////////////////////////////////////////////////////////
int b[100001];
void sub3()
{
    int sl=0;
    for(i=2;i<=n;i++) b[++sl]=t[i]-(t[i-1]+1);
    sort(b+1,b+sl+1);
    long long sum=0;
    for(i=sl;i>=sl-(m-1)+1;i--) sum+=b[i];
    cout<<t[n]+1-t[1]-sum;
}
int main()
{
    //freopen("stove.inp","r",stdin);
    //freopen("stove.out","w",stdout);
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>t[i];
    if(n<=20) sub1();
    else if(n<=5000) sub2();
    else sub3();
}

Compilation message (stderr)

stove.cpp: In function 'void vet(int, int)':
stove.cpp:13:46: warning: 'vt' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(j==n || d[j+1]==1) sum+=t[j]+1-vt;
                                        ~~~~~~^~~

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