Submission #1101468

#TimeUsernameProblemLanguageResultExecution timeMemory
1101468huydeptraiso1vutruvnK blocks (IZhO14_blocks)C++14
53 / 100
1080 ms84816 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]; int dp[nmax + 10][105]; void input() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; } void RMQ() { for (int i = 1; i <= n; i++) b[i][0] = a[i]; for (int j = 1; (1 << j) <= n; j++) { for (int i = 0; i + (1 << j) - 1 <= n; i++) { b[i][j] = max(b[i][j - 1] , b[i + (1 << (j - 1))][j - 1]); } } } int get(int l , int r) { int k = __lg(r - l + 1); return max(b[l][k] , b[r - (1 << k) + 1][k]); } void process() { memset(dp , 0x3f , sizeof(dp)); dp[0][0] = 0; for (int i = 1; i <= k; i++) { for (int j = i; j <= n; j++) { for (int h = i; h <= j; h++) { dp[i][j] = min(dp[i][j] , dp[i - 1][h - 1] + get(h , j)); } } } cout << dp[k][n]; } signed main() { faster // freopen ("TASK.INP", "r", stdin); // freopen ("TASK.OUT", "w", stdout); input(); RMQ(); 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...