oj.uz

Submission #886822

# Submission time Handle Problem Language Result Execution time Memory
886822 2023-12-13T02:56:00 Z AlphaMale06 K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 1112 KB 
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

const int N = 100005;
const int K = 103;
const int inf=1e9;
int dp[N], ndp[N], pos[N], lg[N];
int sp[N][17];

int get(int l, int r){
    if(l>r)return 0;
    int rng=r-l+1;
    int lga=lg[rng];
    return max(sp[l][lga], sp[r-(1<<lga)+1][lga]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i=0; i< n; i++)cin >> a[i];
    int mx=0;
    lg[1]=0;
    for(int i=2; i<N; i++){
        lg[i]=lg[i/2]+1;
    }
    for(int i=0; i< n; i++){
        mx=max(mx, a[i]);
        dp[i]=mx;
        sp[i][0]=a[i];
    }
    for(int j=1; j<17; j++){
        for(int i=0; i+(1<<j)<=n; i++){
            sp[i][j]=max(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
        }
    }
    stack<pair<int, int>> st;
    st.push({inf, -1});
    for(int i=0; i< n; i++){
        while(!st.empty() && st.top().F<=a[i]){
            st.pop();
        }
        pos[i]=st.top().S+1;
        st.push({a[i], i});
    }
    while(!st.empty())st.pop();

    for(int j=2; j<=k; j++){
        st.push({inf, -1});
        for(int i=0; i< n; i++){
            int ps=pos[i];
            pair<int, int> lst={-2, -1};
            while(ps<=st.top().S){
                lst=st.top();
                st.pop();
                if(st.size()==0)break;
            }
            if(st.size()==0)st.push(lst);
            else if(lst.F!=-2 && st.top().F+get(st.top().S+1, i)>lst.F+get(lst.S+1, i))st.push(lst);
            ndp[i]=st.top().F+get(st.top().S+1, i);
            while(!st.empty() && st.top().F>= dp[i])st.pop();
            if(dp[i]<ndp[i])st.push({dp[i], i});
        }
        while(!st.empty())st.pop();
        for(int i=0; i< n; i++){
            dp[i]=ndp[i];
        }
    }
    cout << dp[n-1] << '\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 1 ms 720 KB Output is correct
16 Incorrect 0 ms 860 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 1 ms 720 KB Output is correct
16 Incorrect 0 ms 860 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 1 ms 720 KB Output is correct
16 Incorrect 0 ms 860 KB Output isn't correct
17 Halted 0 ms 0 KB -