Submission #829210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829210	2023-08-18T06:36:22 Z	arush_agu	K blocks (IZhO14_blocks)	C++17	18 / 100	1 ms	340 KB

blocks

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#ifdef DEBUG
#include <time.h>
#endif
 
#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif
 
using namespace std;
using namespace __gnu_pbds;
 
typedef pair<int, int> ii;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;
 
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;
 
typedef vector<bool> vb;
 
template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;
 
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}
 
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-9;
 
struct ST {
  const int MAXLG = 22;
  int n;
  vvl t;
  vl lg2;
 
  ST(vl &a) : n(a.size()) {
    t = vvl(MAXLG, vl(n));
    t[0] = a;
 
    for (int j = 1; j < MAXLG; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        t[j][i] = max(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
 
    lg2 = vl(n + 10);
    lg2[1] = 0;
    for (int i = 2; i <= n; i++)
      lg2[i] = lg2[i / 2] + 1;
  }
 
  ll query(int l, int r) {
    if (l > r)
      swap(l, r);
 
    int k = lg2[r - l + 1];
    return max(t[k][l], t[k][r - (1 << k) + 1]);
  }
};
 
void solve() {
  int n, k;
  cin >> n >> k;
  vl a(n);
  for (ll &x : a)
    cin >> x;
 
  ST st(a);
 
  vvl dp(k + 1, vl(n, INF));
  for (int i = 0; i < n; i++)
    dp[1][i] = i == 0 ? a[i] : max(a[i], dp[1][i - 1]);
 
  function<void(int, int, int, int, int)> f = [&](int l, int r, int k,
                                                  int opt_l, int opt_r) {
    if (l > r)
      return;
 
    int mid = (l + r) / 2;
    llll best = {INF, INF};
 
    for (int i = max(opt_l - 70, k - 1); i <= min(mid, opt_r + 70); i++)
      best = min(best, {dp[k - 1][i - 1] + st.query(i, mid), i});
 
    assert(best.second != INF);
 
    dp[k][mid] = best.first;
    f(l, mid - 1, k, opt_l, best.second);
    f(mid + 1, r, k, best.second, opt_r);
  };
 
  for (int kk = 2; kk <= k; kk++)
    f(kk - 1, n - 1, kk, 0, n - 1);
 
  cout << dp[k].back() << '\n';
}
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
 
  clock_t start = clock();
 
  int test_cases = 1;
  // cin >> test_cases;
 
  while (test_cases--)
    solve();
 
#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:162:11: warning: unused variable 'start' [-Wunused-variable]
  162 |   clock_t start = clock();
      |           ^~~~~

Subtask #1
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct
11	Correct	212 KB	Output is correct
12	Correct	340 KB	Output is correct
13	Correct	212 KB	Output is correct
14	Correct	340 KB	Output is correct
15	Correct	340 KB	Output is correct
16	Incorrect	340 KB	Output isn't correct
17	Halted	0 KB	-

Subtask #2
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct

Subtask #3
0 / 21.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct
11	Correct	212 KB	Output is correct
12	Correct	340 KB	Output is correct
13	Correct	212 KB	Output is correct
14	Correct	340 KB	Output is correct
15	Correct	340 KB	Output is correct
16	Incorrect	340 KB	Output isn't correct
17	Halted	0 KB	-

Subtask #4
0 / 47.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct
11	Correct	212 KB	Output is correct
12	Correct	340 KB	Output is correct
13	Correct	212 KB	Output is correct
14	Correct	340 KB	Output is correct
15	Correct	340 KB	Output is correct
16	Incorrect	340 KB	Output isn't correct
17	Halted	0 KB	-

Submission #829210

Compilation message

Subtask #1 0 / 14.0

Subtask #2 18.0 / 18.0

Subtask #3 0 / 21.0

Subtask #4 0 / 47.0

Subtask #1
0 / 14.0

Subtask #2
18.0 / 18.0

Subtask #3
0 / 21.0

Subtask #4
0 / 47.0