Submission #1254655

#TimeUsernameProblemLanguageResultExecution timeMemory
1254655thuhienneK개의 묶음 (IZhO14_blocks)C++20
100 / 100
116 ms2992 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr); #define MULTEST int tt;cin >> tt;while (tt--) solve(); int n,k,arr[100009]; namespace sub2 { bool check() { return n <= 20; } void solve() { long long ret = 1e18; for (int mask = 0;mask < (1 << (n - 1));mask++) if (__builtin_popcount(mask) == k - 1) { long long curr = 0; int maxval = arr[1]; for (int i = 0;i < n - 1;i++) { if (mask >> i & 1) { curr += maxval; maxval = arr[i + 2]; } else maxval = max(maxval,arr[i + 2]); } curr += maxval; ret = min(ret,curr); } cout << ret; } } namespace sub13 { bool check() { return n <= 100; } long long dp[109][109]; void solve() { for (int i = 1;i <= k;i++) dp[0][i] = 1e18; for (int i = 1;i <= n;i++) { dp[i][0] = 1e18; for (int j = 1;j <= k;j++) { dp[i][j] = 1e18; int maxval = -1e9; for (int d = i;d >= 1;d--) { maxval = max(maxval,arr[d]); dp[i][j] = min(dp[i][j],dp[d - 1][j - 1] + maxval); } } } cout << dp[n][k]; } } namespace sub4 { bool check() { return 1; } long long prev[100009],dp[100009]; stack <pair<int,long long>> st; void solve() { for (int i = 1;i <= n;i++) { dp[i] = max(dp[i - 1],1ll*arr[i]); } dp[0] = 1e18; arr[0] = 1e9; for (int tt = 2;tt <= k;tt++) { while (st.size()) st.pop(); st.push({0,1e18}); for (int i = 0;i <= n;i++) prev[i] = dp[i],dp[i] = 1e18; for (int i = 1;i <= n;i++) { pair <int,long long> hien = {i,prev[i]}; long long val = 1e18; while (arr[st.top().first] <= arr[i]) { hien.second = min(hien.second,st.top().second); val = min(val,st.top().second); st.pop(); } val = min(val,prev[st.top().first]); dp[i] = min(val + arr[i],dp[st.top().first]); st.push(hien); } } cout << dp[n]; } } int main() { FastIO // MULTEST // freopen("blocks.inp","r",stdin); // freopen("blocks.out","w",stdout); cin >> n >> k; for (int i = 1;i <= n;i++) cin >> arr[i]; if (sub2::check()) { sub2::solve(); return 0; } if (sub13::check()) { sub13::solve(); return 0; } if (sub4::check()) { sub4::solve(); return 0; } } /* Nho doi vai em gay co gai ay ngoi duoi goc pho nen tho ... */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...