Submission #1101545

#TimeUsernameProblemLanguageResultExecution timeMemory
1101545huydeptraiso1vutruvnK blocks (IZhO14_blocks)C++14
0 / 100
12 ms86812 KiB
#include <bits/stdc++.h> #define fi first #define se second #define int long long #define pii pair<int,int> #define pb push_back #define bit(mask,i) ((mask >> i) & 1) #define mask(i) (1 << (i)) #define lcm(a,b) ((a*b)/__gcd(a,b)) #define turn_on(mask,i) ((mask | (1 << i)) #define turn_off(mask,i) (mask ^ (1 << i)) #define count_1(x) __builtin_popcount(x) #define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); using namespace std; const int Base = 37; const int MOD = 1e9 + 7; const int nmax = 1e5; const int size = 320; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int n, k; int a[nmax + 10], b[nmax + 10][20], l[nmax + 10]; int dp[nmax + 10][105]; void input() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; } int get(int l , int r) { int k = __lg(r - l + 1); return min(b[l][k] , b[r - (1 << k) + 1][k]); } void process() { stack <int> st; st.push(0); a[0] = 1e9; for (int i = 1; i <= n; i++) { while ( a[st.top()] <= a[i]) st.pop(); l[i] = st.top(); st.push(i); } memset(dp , 0x3f , sizeof(dp)); dp[0][0] = 0; for (int j = 1; j <= k; j++) { for (int i = 0; i <= n; i++) b[i][0] = dp[i][j - 1]; for (int k = 1; (1 << k) <= n; k++) { for (int i = 0; i + (1 << k) - 1 <= n; i++) { b[i][k] = min(b[i][k - 1] , b[i + (1 << (k - 1))][k - 1]); } } for (int i = 1; i <= n; i++) { dp[i][j] = min(dp[i][j] , get(l[i] , i - 1) + a[i]); dp[i][j] = min(dp[i][j] , dp[i][l[j]]); } } cout << dp[n][k]; } signed main() { faster // freopen ("TASK.INP", "r", stdin); // freopen ("TASK.OUT", "w", stdout); input(); process(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...