oj.uz

Submission #797365

# Submission time Handle Problem Language Result Execution time Memory
797365 2023-07-29T10:02:47 Z detroiddh K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 340 KB 
#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

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.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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