oj.uz

Submission #885569

# Submission time Handle Problem Language Result Execution time Memory
885569 2023-12-10T07:47:13 Z 12345678 K blocks (IZhO14_blocks) C++17
0 / 100
 2 ms 6492 KB 
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    v[0]=1e9;
    for (int i=1; i<=n; i++) cin>>v[i], mx=max(mx, v[i]), dp[1][i]=mx;
    for (int i=2; i<=k; i++)
    {
        stack<pair<int, int>> s;
        for (int j=i; j<=n; j++)
        {
            int vl=dp[i-1][j-1];
            while (!s.empty()&&s.top().first<=v[j]) vl=min(vl, s.top().second), s.pop();
            dp[i][j]=vl+v[j];
            if (!s.empty()) vl=min(vl, s.top().first+s.top().second);
            if (s.empty()) s.push({v[j], vl});
            else if (s.top().first+s.top().second>v[j]+vl) s.push({v[j], vl});
        }
    }
    cout<<dp[k][n];
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 1 ms 4440 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4528 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4556 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Incorrect 1 ms 6492 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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