oj.uz

Submission #857416

# Submission time Handle Problem Language Result Execution time Memory
857416 2023-10-06T07:25:14 Z TrinhKhanhDung K blocks (IZhO14_blocks) C++14
0 / 100
 11 ms 84972 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) v.begin(),v.end()
#define v1 vector<ll>
#define v2 vector<vector<ll>>
#define MAX_M (int)20003
#define MOD (ll)(998244353)
#define INF (int)1e9
#define oo (ll)1e18

template <class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template <class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

using namespace std;

const int MAX = 1e5 + 3;
const int MAX_K = 1e2 + 3;

int N, K;
int a[MAX], d[MAX][18], Max[MAX][18];
ll f[103][MAX];

ll w(int id, int l, int r)
{
    int delta = r - l + 1;
    ll ans = 0;
    int u = r;
    for(int tmp=delta; tmp>0; tmp-=tmp&-tmp){
        int i = __builtin_ctz(tmp);
        maximize(ans, Max[u][i]);
        u = d[u][i];
    }
    return ans + f[id][l - 1];
}

struct Info
{
    int p, l, r;
};

void solve(int id)
{

    deque<Info> dq;
    dq.push_back({1, 1, N});

    for(int i=1; i<=N; i++){
        f[id][i] = w(id - 1, dq.front().p, i);
        if(i == N) break;
        if(dq.front().r == i) dq.pop_front();
        else dq.front().l++;

        while(!dq.empty() && w(id - 1, dq.back().p, dq.back().l) >= w(id - 1, i + 1, dq.back().l)) dq.pop_back();

        if(dq.empty()) dq.push_back({i + 1, i + 1, N});
        else {
            int L = dq.back().l, R = dq.back().r, index;
            while(L <= R){
                int M = (L + R) >> 1;
                if(w(id - 1, dq.back().p, M) < w(id - 1, i + 1, M)){
                    index = M;
                    L = M + 1;
                } else R = M - 1;
            }
            dq.back().r = index;
            if(index < N){
                dq.push_back({i + 1, index + 1, N});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    for(int i=1; i<=N; i++){
        cin >> a[i];
    }

    for(int i=1; i<=N; i++){
        d[i][0] = i-1;
        for(int j=1; j<=17; j++){
            d[i][j] = d[d[i][j-1]][j-1];
        }

        Max[i][0] = a[i];
        for(int j=1; j<=17; j++){
            Max[i][j] = max(Max[i][j-1], Max[d[i][j-1]][j-1]);
        }
    }

    memset(f, 0x3f, sizeof f);

    f[0][0] = 0;
    for(int j=1; j<=K; j++){
        solve(j);
    }

    cout << f[K][N];

    return 0;
}

Compilation message

blocks.cpp: In function 'void solve(int)':
blocks.cpp:79:25: warning: 'index' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |             dq.back().r = index;
      |             ~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 84572 KB Output is correct
2 Correct 9 ms 84668 KB Output is correct
3 Correct 10 ms 84568 KB Output is correct
4 Correct 10 ms 84696 KB Output is correct
5 Correct 9 ms 84572 KB Output is correct
6 Correct 10 ms 84568 KB Output is correct
7 Correct 9 ms 84572 KB Output is correct
8 Correct 9 ms 84684 KB Output is correct
9 Correct 10 ms 84572 KB Output is correct
10 Correct 10 ms 84660 KB Output is correct
11 Incorrect 9 ms 84572 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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