//Suleyman Atayew
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define N 100010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <int, int>
using namespace std;
int n, k;
int v[N];
//int MX[N];
//int T[N*4];
//int L[N*4];
int dp[110][N];
//void init(int l, int r, int node)
//{
// L[node] = 0;
// T[node] = 1e9;
//
// if(l == r) return;
//
// init(l, (l+r)/2, node*2);
// init((l+r)/2+1, r, node*2+1);
//}
//
//void upd2(int x, int y, int l, int r, int node)
//{
// if(l == r) {
// T[node] = dp[x][l];
// return;
// }
//
// if(y <= (l+r)/2)
// upd2(x, y, l, (l+r)/2, node*2);
// else
// upd2(x, y, (l+r)/2+1, r, node*2+1);
//
// T[node] = min(T[node*2], T[node*2+1]);
//
// if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
// else L[node] = L[node*2+1];
//}
//shift(int node, int to)
//{
// T[to] -= L[to];
// T[to] += L[node];
// L[to] = L[node];
//}
//void upd(int a, int b, int x, int l, int r, int node)
//{
// if(l > b || r < a) return;
//
// if(l >= a && r <= b) {
// if(l == r) {
// T[node] -= L[node];
// T[node] += x;
// L[node] = x;
// return;
// }
//
// L[node] = x;
//
// shift(node, node*2);
// shift(node, node*2+1);
//
// T[node] = min(T[node*2], T[node*2+1]);
//
// if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
// else L[node] = L[node*2+1];
//
// return;
// }
//
// shift(node, node*2);
// shift(node, node*2+1);
// L[node] = 0;
//
// upd(a, b, x, l, (l+r)/2, node*2);
// upd(a, b, x, (l+r)/2+1, r, node*2+1);
//
// T[node] = min(T[node*2], T[node*2+1]);
//
// if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
// else L[node] = L[node*2+1];
//}
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
// vector <int> E;
// for(int i = 1; i <= n; i++) {
// while(!E.empty() && v[E.back()] < v[i])
// E.pop_back();
//
// if(E.empty()) MX[i] = 0;
// else {
// if(v[E.back()] == v[i]) MX[i] = MX[E.back()];
// else MX[i] = E.back()+1;
// }
//
// E.pb(i);
// }
// for(int i = 1; i <= n; i++) dp[0][i] = 1e9;
//
// for(int i = 1; i <= k; i++) {
// init(0, n, 1);
//
// for(int h = 0; h <= n; h++) {
// if(h < i) {
// dp[i][h] = 1e9;
//
// upd2(i-1, h, 0, n, 1);
//
// continue;
// }
//
// upd(MX[h], h-1, v[h], 0, n, 1);
//
// dp[i][h] = T[1];
//
// upd2(i-1, h, 0, n, 1);
// }
// }
cout << dp[k][n] << "\n";
}
Compilation message
blocks.cpp: In function 'int main()':
blocks.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &v[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
