Submission #1186790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186790		ElayV13	K blocks (IZhO14_blocks)	C++20	53 / 100	1091 ms	2632 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define FOR(a , b) for(int i = a;i <= b;i++)
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e18;
const int mod = 1e9 + 7;

const int N = 1e5 + 1;

int n , k , a[N] , st[N * 4];

void build(int idx , int l , int r)
{
        if(l == r){
                st[idx] = a[l];
                return;
        }
        int mid = (l + r) >> 1;
        build(2 * idx , l , mid);
        build(2 * idx + 1 , mid + 1 , r);
        st[idx] = max(st[2 * idx] , st[2 * idx + 1]);
}

int ask(int idx , int l , int r , int ql , int qr)
{
        if(ql > r or l > qr) return -INF;
        else if(ql <= l && r <= qr){
                return st[idx];
        }
        int mid = (l + r) >> 1;
        return max(ask(2 * idx , l , mid , ql , qr) , ask(2 * idx + 1 , mid + 1 , r , ql , qr));
}

int get(int l , int r)
{
        if(l > r) return 0;
        return ask(1 , 1 , n , l , r);
}

signed main(){
      ios_base::sync_with_stdio(0);
      cin.tie(0);cout.tie(0);
      cin >> n >> k;
      int MX = -1;
      for(int i = 1;i <= n;i++)
      {
              cin >> a[i];
              MX = max(MX , a[i]);
      }
      if(k == 1)
      {
              cout << MX << endl;
              return 0;
      }
      build(1 , 1 , n);
      vector < vector < int > > dp(k , vector < int > (n + 1 , INF));
      for(int i = 1;i <= n;i++)
      {
              int q = (n - i);
              if(q + 1 < k) continue;
              dp[1][i] = get(1 , i);
      }
      for(int c = 2;c <= k - 1;c++)
      {
              for(int i = 1;i <= n;i++)
              {
                      int q = (n - i);
                      if(c + q < k) continue;
                      for(int j = c - 1;j <= i - 1;j++)
                      {
                              int Q = (n - j);
                              int C = c - 1;
                              if(C + Q < k) continue;
                              dp[c][i] = min(dp[c][i] , dp[c - 1][j] + get(j + 1 , i));
                      }
              }
      }
      int res = INF;
      for(int i = 1;i <= n;i++)
      {
              res = min(res , dp[k - 1][i] + get(i + 1 , n));
      }
      cout << res << endl;
}

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