oj.uz

Submission #410840

# Submission time Handle Problem Language Result Execution time Memory
410840 2021-05-23T19:51:04 Z MasterTaster K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXX 100000000010LL
#define MAXN 100010
#define MAXK 110

using namespace std;

ll seg[MAXK][4*MAXN], dp[MAXN][MAXK], a[MAXN];
int n, k, lv[MAXN];

ll query(int i, int node, int l, int r, int levo, int desno)
{
    if (levo>r || desno<l) return MAXX;
    if (levo<=l && desno>=r) return seg[i][node];

    int mid=l+(r-l)/2;
    return min(query(i, 2*node, l, mid, levo, desno),
               query(i, 2*node+1, mid+1, r, levo, desno));
}
void upd(int i, int node, int l, int r, int pos, ll val)
{
    if (pos>r || pos<l) return;
    if (l==r) { seg[i][node]=val; return; }

    int mid=l+(r-l)/2;
    upd(i, 2*node, l, mid, pos, val);
    upd(i, 2*node+1, mid+1, r, pos, val);
    seg[i][node]=min(seg[i][2*node], seg[i][2*node+1]);
}

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

    cin>>n>>k;

    for (int i=1; i<=n; i++) cin>>a[i];

    stack<pii> st;
    st.push({1000010, 1});
    lv[1]=1;
    for (int i=2; i<=n; i++)
    {
        while (st.top().xx<a[i]) st.pop();
        lv[i]=st.top().yy;
        //cout<<lv[i]<<" ";

        st.push({a[i], i});
    }
    //cout<<endl;

    for (int i=0; i<=n; i++) for (int j=0; j<=k; j++) { dp[i][j]=MAXX; upd(j, 1, 0, n-1, max(0, i-1), MAXX); }

    dp[1][1]=a[1]; upd(1, 1, 0, n-1, 0, dp[1][1]);
    for (int i=2; i<=n; i++)
    {
        //cout<<i<<endl;
        for (int j=1; j<=min(k, i); j++)
        {
            //cout<<"trazim "<<j-1<<" "<<lv[i]-1<<" "<<i-2<<endl;
            dp[i][j]=query(j-1, 1, 0, n-1, max(lv[i]-1, 0), i-1)+a[i];
            //cout<<dp[i][j]<<" ";
            dp[i][j]=min(dp[i][j], dp[lv[i]][j]);
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }

        for (int j=1; j<=min(k, i); j++) { /*cout<<"apdejtujem "<<j<<" "<<i-1<<endl;*/ upd(j, 1, 0, n-1, i-1, dp[i][j]); }
    }

    cout<<dp[n][k];

}

/*
5 3
1 | 4 2 5 | 3
*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -