Submission #1198181

#TimeUsernameProblemLanguageResultExecution timeMemory
1198181dangheoK blocks (IZhO14_blocks)C++20
53 / 100
1098 ms59268 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 SegTree{ int n; ll st[mmn]; void SetN(int N){ n = N; fill(st + 1, st + 4 * n + 10, 9e18); } void DoUpdate(int l, int r, int id, const int &x, const ll &y){ if(l > x || r < x) return; if(l == r){ st[id] = min(st[id], y); return; } int mid = (l + r) / 2; DoUpdate(l, mid, id * 2, x, y); DoUpdate(mid + 1, r, id * 2 + 1, x, y); st[id] = min(st[id * 2], st[id * 2 + 1]); } inline void update(const int &x, const ll &y){ DoUpdate(0, n + 1, 1, x, y); } ll Query(int l, int r, int id, int u, int v){ if(l > v || r < u) return 9e18; if(u <= l && r <= v) return st[id]; int mid = (l + r) / 2; return min(Query(l, mid, id * 2, u, v), Query(mid + 1, r, id * 2 + 1, u, v)); } inline ll getMin(const int &x, const int &y){ return Query(0, n + 1, 1, x, y); } } segtree; 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 & l[i] < r[k]) // -> update(r[i], dp[j][i]) // getMin(l[i] + 1, n + 1) ll mx = -9e18; for(int i = 1; i <= n; ++i) dp[1][i] = mx = max(mx, a[i]); for(int j = 2; j <= k; ++j){ segtree.SetN(n + 1); segtree.update(r[j - 1], dp[j - 1][j - 1]); for(int i = j; i <= n; ++i){ dp[j][i] = segtree.getMin(l[i] + 1, n + 1) + a[i]; segtree.update(r[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 = k; i <= n; ++i) if(r[i] >= n + 1) 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...