# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
442932 | 2021-07-09T11:19:14 Z | BeanZ | K blocks (IZhO14_blocks) | C++14 | 1 ms | 332 KB |
// I_Love_LPL 11m #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 1e5 + 5; long long mod = 1000007; const int lim = 4e5 + 5; const int lg = 20; const int base = 311; const long double eps = 1e-6; ll mx[N][lg + 1], dp[N][105], a[N]; ll get(ll l, ll r){ ll l2 = __lg(r - l + 1); return max(mx[l][l2], mx[r - (1 << l2) + 1][l2]); } void DP(ll t, ll l, ll r, ll optl, ll optr){ if (l > r) return; ll mid = (l + r) >> 1; dp[mid][t] = 1e18; ll opt; for (int i = optl; i <= min(optr, mid - 1); i++){ ll cost = dp[i][t - 1] + get(i + 1, mid); if (dp[mid][t] > cost){ dp[mid][t] = cost; opt = i; } } DP(t, l, mid - 1, optl, opt); DP(t, mid + 1, r, opt, optr); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n, k; cin >> n >> k; for (int i = 1; i <= n; i++){ cin >> a[i]; mx[i][0] = a[i]; } for (int i = 1; i <= lg; i++){ for (int j = 1; (j + (1 << i) - 1) <= n; j++){ mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]); } } for (int i = 1; i <= n; i++){ dp[i][1] = max(dp[i - 1][1], a[i]); } for (int i = 2; i <= k; i++){ DP(i, 1, n, 1, n); } cout << dp[n][k]; } /* Ans: Out: */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Incorrect | 0 ms | 332 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Incorrect | 0 ms | 332 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Incorrect | 0 ms | 332 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Incorrect | 0 ms | 332 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |