oj.uz

Submission #487727

# Submission time Handle Problem Language Result Execution time Memory
487727 2021-11-16T13:12:27 Z stefantaga Stove (JOI18_stove) C++14
0 / 100
 0 ms 204 KB 
#include <bits/stdc++.h>

using namespace std;
long double mini,v[100005];
int n,k,i,j;
long double st,dr,mij;
typedef long double 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

stove.cpp: In function 'std::pair<long double, long double> 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -