| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 536675 |
2022-03-13T19:13:07 Z |
blue |
K blocks (IZhO14_blocks) |
C++17 |
|
1 ms |
324 KB |
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())
const ll INF = 1'000'000'000'000'000LL;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
vll A(1+N, INF);
for(int i = 1; i <= N; i++) cin >> A[i];
ll* DP[1+K];
DP[0] = new ll[1+N];
DP[1] = new ll[1+N];
for(int k = 2; k <= K; k++)
{
DP[k] = DP[k-2];
}
for(int i = 1; i <= N; i++)
{
DP[0][i] = DP[1][i] = +INF;
}
DP[0][0] = 0;
for(int k = 1; k <= K; k++)
{
// cerr << "\n\n\n\n\n k = " << k << '\n';
vector<int> mxp;
vector<ll> mndp;
// DP[k][0] = 0;
DP[k][0] = INF;
for(int i = 1; i <= N; i++)
{
// cerr << "\n\n\n";
// cerr << "i = " << i << '\n';
// cerr << "push value " << k-1 << ' ' << i-1 << " : " << DP[k-1][i-1] << '\n';
mxp.push_back(i-1);
if(mndp.empty())
mndp.push_back(DP[k-1][max(i-1, k-1)] + A[i]);
else
mndp.push_back(min(mndp.back(), DP[k-1][max(i-1, k-1)] + A[i]));
// cerr << "push P " << mndp.back() << '\n';
while(A[mxp.back()] <= A[i])
{
// cerr << "pop A " << mndp.back() << '\n';
mxp.pop_back();
mndp.pop_back();
}
// cerr << "pop B " << mndp.back() << '\n';
mndp.pop_back();
if(mndp.empty())
mndp.push_back(DP[k-1][max(mxp.back(), k-1)] + A[i]);
else
mndp.push_back(min(mndp.back(), DP[k-1][max(mxp.back(), k-1)] + A[i]));
// cerr << "push Q " << mndp.back() << '\n';
DP[k][i] = mndp.back();
// cerr << k << ' ' << i << " : " << DP[k][i] << '\n';
}
}
cout << DP[K][N] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
324 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
