Submission #487667

#	Time	Username	Problem	Language	Result	Execution time	Memory
487667		stefantaga	Stove (JOI18_stove)	C++14	50 / 100	1090 ms	2708 KiB

stove

#include <bits/stdc++.h>

using namespace std;
long long din[2][100005];
long long mini,v[100005];
int n,k,i,j;
int min1(int a,int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}
void divide(int st,int dr,int mxst,int mxdr,int acum,int inainte)
{
    if (st>dr)
    {
        return;
    }
    int mij=(st+dr)/2,poz;
    long long mini=1e12,lim=min1(mxdr,mij);
    din[acum][mij]=1e12;
    for (int i=mxst;i<=lim;i++)
    {
        if (v[mij]-v[i]+1+din[inainte][i-1]<din[acum][mij])
        {
            din[acum][mij]=v[mij]-v[i]+1+din[inainte][i-1];
            poz=i;
        }
    }
    divide(st,mij-1,mxst,poz,acum,inainte);
    divide(mij+1,dr,poz,mxdr,acum,inainte);
}
int main()
{
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>k;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        din[1][i]=v[i]-v[1]+1;
    }
    for (i=2;i<=k;i++)
    {
        int acum,inainte;
        acum=i%2;
        inainte=1-acum;
        divide(1,n,1,n,acum,inainte);
    }
    cout<<din[k%2][n];
    return 0;
}

Compilation message (stderr)

stove.cpp: In function 'void divide(int, int, int, int, int, int)':
stove.cpp:22:15: warning: unused variable 'mini' [-Wunused-variable]
   22 |     long long mini=1e12,lim=min1(mxdr,mij);
      |               ^~~~
stove.cpp:32:11: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |     divide(st,mij-1,mxst,poz,acum,inainte);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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