Submission #797365

#	Time	Username	Problem	Language	Result	Execution time	Memory
797365		detroiddh	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	340 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const ll maxn = 1e5 + 3 , maxk = 103;
const ll mod = 1e9 + 7;

ll n , k;
ll a[maxn] , dp[maxk][maxn] , inf = 1e18;

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

ll st[4 * maxn];

ll constructST(ll si , ll l , ll r)
{
    if(l == r)
    {
        st[si] = a[l];
        return a[l];
    }

    ll mid = (l + r) / 2;

    st[si] = max(constructST(si * 2 , l , mid) , constructST(si * 2 + 1 , mid + 1 , r));

    return st[si];
}

ll getmax(ll si , ll sl , ll sr , ll l , ll r)
{
    if(l <= sl && sr <= r) return st[si];

    if(l > sr || r < sl) return -inf;

    ll mid = (sl + sr) / 2;

    return max(getmax(si * 2 , sl , mid , l , r) , getmax(si * 2 + 1 , mid + 1 , sr , l , r));
}

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

ll cost(int i , int j)
{
    return getmax(1 , 1 , n , i , j);
}

void solve(int id , int l , int r , int opl , int opr)
{
   if(l > r) return;
   int mid = (l + r) / 2;
   dp[id][mid] = inf;
   int optm;
   for(int i = opl ; i <= opr ; ++i)
   {
       if(i > mid) continue;
       ll so = dp[id - 1][i - 1] + cost(i , mid);
       if(dp[id][mid] > so)
       {
           dp[id][mid] = so;
           optm = i;
       }
   }

   solve(id , l , mid - 1 , opl , optm);
   solve(id , mid + 1 , r , optm , opr);
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen("","r",stdin);
   //freopen("","w",stdout);

   cin>>n>>k;

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

   constructST(1 , 1 , n);

   for(int i = 1 ; i <= k ; ++i) dp[i][0] = inf;

   for(int i = 1 ; i <= n ; ++i) dp[1][i] = cost(1 , i);
   for(int i = 2 ; i <= k ; ++i) solve(i , 1 , n , 1 , n);

   cout<<dp[k][n];
}

Compilation message (stderr)

blocks.cpp: In function 'void solve(int, int, int, int, int)':
blocks.cpp:66:9: warning: 'optm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |    solve(id , l , mid - 1 , opl , optm);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47