oj.uz

Submission #405162

# Submission time Handle Problem Language Result Execution time Memory
405162 2021-05-15T19:56:40 Z MarcosPauloEvers K blocks (IZhO14_blocks) C++17
0 / 100
 6 ms 404 KB 
#include <bits/stdc++.h>

#define mid(l,r) ((l + r) >> 1)
#define lsb(x) (x & (-x))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define FOR(X,L,R) for(int X=L;X<R;++X)
#define endl '\n'
#define int long long
#define MOD ((int)1e9 + 7)
#define INF (0x3f3f3f3f)
#define LLINF (0x3f3f3f3f3f3f3f3fLL)

using namespace std;

template<typename T>
inline void input(vector<T>& v)
{
    for(T& x: v)
        cin >> x;
}

#define pow2(x) (1LL << x)

class SparceTable
{
private:
    vector< vector<int> > sparce;
    vector<int> log;
    int n, m; // m = ceil(log2(n))
public:
    SparceTable(const vector<int>& v)
    {
        n = v.size();
        m = 1;
        while(pow2(m) < n) m++;

        sparce.assign(n, vector<int>(m, -LLINF));

        for(int i = 0; i < n; i++)
            sparce[i][0] = v[i];
        
        for(int j = 1; j <= m; j++)
        {
            for(int i = 0; i + pow2(j) <= n; i++)
            {
                sparce[i][j] = max(sparce[i][j - 1], sparce[i + pow2(j - 1)][j - 1]);
            }
        }

        log.assign(n + 1, 0);
        
        log[1] = 0;
        for(int i = 3; i <= n; i++)
        {
            log[i] = 1 + log[i / 2];
        }
    }
    int get_max(int i, int j)
    {
        int k = log[j - i + 1];
        return max(sparce[i][k], sparce[j - pow2(k) + 1][k]);
    }
};

void compute(
    array<vector<int>, 2>& dp,
    int curr_dp,
    SparceTable max_st,
    int l,
    int r,
    int optl,
    int optr
)
{
    if(l > r)
    {
        return;
    }
    int m = mid(l, r);
    pair<int, int> best = {LLINF, -1};

    for(int k = optl; k < min(m, optr); k++)
    {
        best = min(best, {dp[1 - curr_dp][k] + max_st.get_max(k + 1, m), k});
    }

    dp[curr_dp][m] = best.first;
    int opt = best.second;

    compute(dp, curr_dp, max_st,   l, m-1, optl,  opt);
    compute(dp, curr_dp, max_st, m+1,   r,  opt, optr);
}

void solve()
{
    int n, k; cin >> n >> k;
    vector<int> v(n); input(v);

    SparceTable sparce(v);

    array< vector<int>, 2> dp;
    dp[0] = vector<int>(n);
    dp[1] = vector<int>(n);

    int curr_dp = 0;

    dp[curr_dp][0] = v[0];
    for(int i = 1; i < n; i++)
    {
        dp[curr_dp][i] = max(dp[curr_dp][i - 1], v[i]);
    }

    curr_dp = 1 - curr_dp;

    for(int i = 2; i <= k; i++)
    {
        compute(dp, curr_dp, sparce, 0, n - 1, 0, n);

        curr_dp = 1 - curr_dp;
    }

    cout << dp[1-curr_dp][n - 1] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    #if defined(CODEFORCES) || defined(CF)
        int t; cin >> t;
        while(t--) solve();
    #else
        solve();
    #endif

    return 0;
}

Compilation message

blocks.cpp: In constructor 'SparceTable::SparceTable(const std::vector<long long int>&)':
blocks.cpp:47:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |                 sparce[i][j] = max(sparce[i][j - 1], sparce[i + pow2(j - 1)][j - 1]);
      |                                                                      ~~^~~
blocks.cpp:23:25: note: in definition of macro 'pow2'
   23 | #define pow2(x) (1LL << x)
      |                         ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Incorrect 6 ms 404 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Incorrect 6 ms 404 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Incorrect 6 ms 404 KB Output isn't correct
14 Halted 0 ms 0 KB -