Submission #487728

#	Time	Username	Problem	Language	Result	Execution time	Memory
487728		stefantaga	Stove (JOI18_stove)	C++14	0 / 100	1 ms	204 KiB

stove

#include <bits/stdc++.h>

using namespace std;
long double mini,v[100005];
int n,k,i,j;
long double st,dr,mij;
typedef long long ll;
ll din[200005],cnt[200005];
pair <ll,ll> ceau(ll alpha)
{
     int i,poz;
     for (i=1;i<=n;i++)
     {
         din[i]=cnt[i]=0;
     }
     din[1]=1+alpha;
     cnt[1]=1;
     ll minim=1e16;
     for (i=2;i<=n;i++)
     {
         din[i]=v[i]-v[i-1]+din[i-1];
         cnt[i]=cnt[i-1];
         if (din[i-1]-v[i]<minim)
         {
             minim=din[i-1]-v[i];
             poz=i;
         }
         if (v[i]+minim+1+alpha<din[i])
         {
             din[i]=v[i]+minim+1+alpha;
             cnt[i]=cnt[poz-1]+1;
         }
         else
         if (v[i]+minim+1+alpha==din[i])
         {
             cnt[i]=min(cnt[i],cnt[poz-1]+1);
         }
     }
     return {din[n],cnt[n]};
}
ll sol;
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];
    }
    st=-1e12;
    dr=1e12;
    while (dr-st>1e-6)
    {
        mij=(st+dr)/2;
        auto sal =ceau(mij);
        if (sal.second<=k)
        {
            sol=sal.first-mij*sal.second;
            dr=mij;
        }
        else
        {
            st=mij;
        }
    }
    cout<<sol;
    return 0;
}

Compilation message (stderr)

stove.cpp: In function 'std::pair<long long int, long long int> ceau(ll)':
stove.cpp:31:28: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |              cnt[i]=cnt[poz-1]+1;
      |                         ~~~^~

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