Submission #810820

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

blocks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template < class key, class compare = less < key > >
using indexed_set = tree < key, null_type, compare, rb_tree_tag,
                           tree_order_statistics_node_update >;

int
main ()
{
  ios::sync_with_stdio (false);
  cin.tie (nullptr);
  int n, k;
  cin >> n >> k;
  vector < int > a (n);
  for (auto &x : a) cin >> x;
  vector < vector < pair < int, int > > > dp (n, vector < pair < int, int > > (k, { -1, -1 }));
  dp[0][0] = { 0, a[0] };
  for (int i = 1; i < n; ++i)
    for (int j = 0; j < k; ++j)
      {
        if (dp[i - 1][j].first != -1)
          {
            dp[i][j] = dp[i - 1][j];
            dp[i][j].second = max (dp[i][j].second, a[i]);
          }
        if (j > 0)
          {
            auto x = dp[i - 1][j - 1];
            x.first += x.second;
            x.second = a[i];
            if (dp[i][j].first == -1 || x.first + x.second < dp[i][j].first + dp[i][j].second)
              dp[i][j] = x;
          }
      };
  cout << dp[n - 1][k - 1].first + dp[n - 1][k - 1].second << '\n';
}

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