Submission #1198210

#TimeUsernameProblemLanguageResultExecution timeMemory
1198210dangheoK blocks (IZhO14_blocks)C++20
100 / 100
317 ms84304 KiB
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <iomanip> #include <numeric> #include <stack> #define hyathu main using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pint = int*; constexpr int mmb = 1e5 + 9, mmn = 4e5 + 69, mmk = 101; const ld pi = atan(1) * 4; const ld golden = (1+sqrtl(5))/2; int n, k; ll a[mmb], dp[mmk][mmb], l[mmb], r[mmb]; //li = so dau tien lon hon ai o ben trai //ri = ... struct FenwickTree{ int n; ll ft[mmn]; void SetN(int N){ n = N; fill(ft + 1, ft + 4 * n + 10, 9e18); } inline void update(int x, const ll &y){ ++x; for(int i = x; i <= n; i += (i & (-i))) ft[i] = min(ft[i], y); } ll getMin(int x){ ++x; ll s = 9e18; for(int i = x; i > 0; i &= (i - 1)) s = min(s, ft[i]); return s; } } fentree; void readData(){ cin >> n >> k; for(int i = 1; i <= n; ++i) cin >> a[i]; } void prepareLR(){ a[0] = a[n + 1] = 9e18; stack <int> st; st.push(0); for(int i = 1; i <= n; ++i){ while(a[i] >= a[st.top()]) st.pop(); l[i] = st.top(); st.push(i); } while(!st.empty()) st.pop(); st.push(n + 1); for(int i = n; i >= 1; --i){ while(a[i] >= a[st.top()]) st.pop(); r[i] = st.top(); st.push(i); } // for(int i = 1; i <= n; ++i) cout << l[i] << " "; // cout << "\n"; // for(int i = 1; i <= n; ++i) cout << r[i] << " "; // cout << "\n"; } void solve(){ prepareLR(); //dp[j][i] = max(dp[j - 1][k] : (i < k & r[i] > l[k]) // -> update(l[i], dp[j - 1][i]) // getMin(r[i] - 1) ll mx = -9e18; for(int i = n; i >= 1; --i) dp[1][i] = mx = max(mx, a[i]); for(int j = 2; j <= k; ++j){ fentree.SetN(n + 1); fentree.update(l[n - j + 2], dp[j - 1][n - j + 2]); for(int i = n - j + 1; i > 0; --i){ dp[j][i] = fentree.getMin(r[i] - 1) + a[i]; fentree.update(l[i], dp[j - 1][i]); } } // for(int j = 1; j <= k; ++j){ // for(int i = 1; i <= n; ++i){ // if(dp[j][i] == 9e18) cout << " * "; // else cout << setw(3) << dp[j][i] << " "; // } // cout << "\n"; // } ll ans = 9e18; for(int i = 1; i <= n - k + 1; ++i) if(l[i] <= 0) ans = min(ans, dp[k][i]); cout << ans; } #define filename "test" int hyathu(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #ifdef dangheo freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); #else //freopen(filename".INP", "r", stdin); //freopen(filename".OUT", "w", stdout); #endif readData(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...