oj.uz

Submission #871940

# Submission time Handle Problem Language Result Execution time Memory
871940 2023-11-12T02:02:32 Z 12345678 K blocks (IZhO14_blocks) C++17
0 / 100
 2 ms 4548 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=105, lx=17;
int n, k, v[nx], dp[kx][nx], mx;

void solve(int l, int r, int ly, int optl, int optr)
{
    if (r<l) return;
    int md=(l+r)/2;
    //cout<<ly<<' '<<l<<' '<<md<<' '<<r<<' '<<optl<<' '<<optr<<'\n';
    pair<int, int> p={1e9, -1};
    mx=0;
    for (int i=md; i>optr; i--) mx=max(mx, v[i]);
    for (int i=min(optr, md); i>=optl; i--) mx=max(mx, v[i]), p=min(p, {mx+dp[ly-1][i-1], i});
    dp[ly][md]=p.first;
    solve(l, md-1, ly, optl, p.second);
    solve(md+1, r, ly, p.second, optr);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>v[i], dp[0][i]=1e9;
    for (int i=1; i<=k; i++) dp[i][0]=1e9, solve(1, n, i, 1, n);
    //for (int i=1; i<=k; i++) for (int j=1; j<=n; j++) cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
    cout<<dp[k][n];
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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